Submission #1602713
Source Code Expand
/In the name of god #include <bits/stdc++.h> #define pb push_back #define F first #define S second using namespace std; typedef long long ll; #define set set1 typedef pair<int,int> pii; const int maxn = 1e5 + 10; int ans[maxn]; int pl[maxn]; int segt[4 * maxn]; int f1[4 * maxn],f2[4 * maxn]; bool has[4 * maxn]; inline int lz1(int v,int s,int e,int val){ f2[v] = 0; has[v] = true; segt[v] = (e - s) * val; f1[v] = val; } inline int lz2(int v,int s,int e,int val){ f2[v] += val; segt[v] += (e - s) * val; } inline int shift(int v,int s,int e){ int lc = 2 * v,rc = 2 * v + 1,m = (e + s) / 2; if (has[v] != false){ lz1(lc,s,m,f1[v]); lz1(rc,m,e,f1[v]); f1[v] = 0; has[v] = false; } if (f2[v] != 0){ lz2(lc,s,m,f2[v]); lz2(rc,m,e,f2[v]); f2[v] = 0; } return 0; } int set(int v,int l,int r,int s,int e,int val){ if ( r<= l) return 0; if (s >= r || e <= l) return 0; if (s >= l && e <= r){ lz1(v,s,e,val); return 0; } shift(v,s,e); int m = (e + s) / 2; set(2 * v,l,r,s,m,val); set(2 * v + 1,l,r,m,e,val); segt[v] = segt[2 * v] + segt[2 * v + 1]; return 0; } int update(int v,int l,int r,int s,int e,int val){ if (r <= l) return 0; if (s >= r || e <= l) return 0; if (s >= l && e <= r){ lz2(v,s,e,val); return 0; } shift(v,s,e); int m = (e + s) / 2; update(2 * v,l,r,s,m,val); update(2 * v + 1,l,r,m,e,val); segt[v] = segt[2 * v] + segt[2 * v + 1]; return 0; } int query(int v,int ind,int s,int e){ if (ind < s || ind >= e) return 0; // cout << v << ' ' << s << ' ' << e << ' ' << segt[v] << endl; if (e - s == 1){ return segt[v]; } shift(v,s,e); int m = (e + s) / 2; return query(2 * v,ind,s,m) + query(2 * v + 1,ind,m,e); } int build(int v,int s,int e){ f1[v] = f2[v] = 0; if (e - s == 1) return 0; int m = (e + s) / 2; build(2 * v,s,m); build(2 * v + 1,m,e); } int q,x; int bs(int lo,int hi,int t,int v){ int m,found = (t == 0) ?lo - 1:hi + 1; while(lo <= hi){ m = (lo + hi) / 2; int as = query(1,m,0,q); if (t){ if (as + v > x){ found = m; hi = m - 1; }else lo = m + 1; }else{ if (as < v){ found = m; lo = m + 1; }else hi = m - 1; } } return found; } int32_t main(){ ios_base::sync_with_stdio(0) , cin.tie(0); int k; cin >> x >> k; int r; vector<int> swp; swp.pb(1e9 + 1); for (int i = 0;i < k;i++){ cin >> r; swp.pb(r); } sort(swp.begin(),swp.end()); cin >> q; int t,a,sz = q - 1; vector<pii> qs; vector<pii> ts; for (int i = 0;i < q;i++){ cin >> t >> a; qs.pb({a,i}); ts.pb({-t,i}); } sort(qs.begin(),qs.end()); sort(ts.begin(),ts.end()); build(1,0,q); for (int i = 0;i < q;i++){ pl[qs[i].S] = i; set(1,i,i + 1,0,q,qs[i].F); } int sw = 0,ca; int lt = 0; for (int i = 0;i < swp.size();i++){ while(sz >= 0 && -ts[sz].F <= swp[i]){ ca = query(1,pl[ts[sz].S],0,q); int t = -ts[sz].F; if (i % 2){ ca = min(x,ca + (t - lt)); }else { ca = max(0ll,ca - (t - lt)); } ans[ts[sz].S] = ca; sz--; ts.pop_back(); } int in = bs(0,q - 1,i % 2,swp[i] - lt); if (i % 2){ set(1,in,q,0,q,x); update(1,0,in,0,q,swp[i] - lt); }else { set(1,0,in + 1,0,q,0); update(1,in + 1,q,0,q,-(swp[i] - lt)); } // cout << in << endl; // for (int i= 0;i < q;i++){ // cout << i << ' ' << query(1,i,0,q) << endl; /// } // cout << endl << endl << endl; lt = swp[i]; } for (int i= 0;i < q;i++){ cout << ans[i] << '\n'; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Sandglass |
User | chaxy_2000 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3593 Byte |
Status | CE |
Compile Error
./Main.cpp:1:1: error: expected unqualified-id before ‘/’ token /In the name of god ^ ./Main.cpp: In function ‘int32_t main()’: ./Main.cpp:148:31: error: no matching function for call to ‘max(long long int, int)’ ca = max(0ll,ca - (t - lt)); ^ In file included from /usr/include/c++/5/bits/char_traits.h:39:0, from /usr/include/c++/5/ios:40, from /usr/include/c++/5/istream:38, from /usr/include/c++/5/sstream:38, from /usr/include/c++/5/complex:45, from /usr/include/c++/5/ccomplex:38, from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:52, from ./Main.cpp:2: /usr/include/c++/5/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&) max(const _Tp& __a, const _Tp& __b) ^ /usr/include/c++/5/bits/stl_algobase.h:219:5: note: template argument deduction/substitution failed: ./Main.cpp:1...