Submission #62272

#TimeUsernameProblemLanguageResultExecution timeMemory
62272BenqCambridge (info1cup18_cambridge)C++11
100 / 100
627 ms33168 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 1<<17; template<class T, int SZ> struct LazySegTree { T sum[2*SZ], mn[2*SZ], lazy[2*SZ]; // set SZ to a power of 2 LazySegTree() { memset (sum,0,sizeof sum); memset (mn,0,sizeof mn); memset (lazy,0,sizeof lazy); } void push(int ind, int L, int R) { sum[ind] += (R-L+1)*lazy[ind]; mn[ind] += lazy[ind]; if (L != R) lazy[2*ind] += lazy[ind], lazy[2*ind+1] += lazy[ind]; lazy[ind] = 0; } void pull(int ind) { sum[ind] = sum[2*ind]+sum[2*ind+1]; mn[ind] = min(mn[2*ind],mn[2*ind+1]); } void build() { F0Rd(i,SZ) pull(i); } T qsum(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) { push(ind,L,R); if (lo > R || L > hi) return 0; if (lo <= L && R <= hi) return sum[ind]; int M = (L+R)/2; return qsum(lo,hi,2*ind,L,M) + qsum(lo,hi,2*ind+1,M+1,R); } T qmin(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) { push(ind,L,R); if (lo > R || L > hi) return INF; if (lo <= L && R <= hi) return mn[ind]; int M = (L+R)/2; return min(qmin(lo,hi,2*ind,L,M), qmin(lo,hi,2*ind+1,M+1,R)); } void upd(int lo, int hi, ll inc, int ind = 1, int L = 0, int R = SZ-1) { push(ind,L,R); if (hi < L || R < lo) return; if (lo <= L && R <= hi) { lazy[ind] = inc; push(ind,L,R); return; } int M = (L+R)/2; upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R); pull(ind); } }; LazySegTree<ll,MX> L; int N,M,key[MX], lst[MX],T[MX],D[MX],ans[MX]; map<pi,int> m; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M; FOR(i,1,N+1) { cin >> T[i] >> D[i]; m[{D[i],i}] = 0; } int co = 0; for (auto& a: m) a.s = co++; FOR(i,1,N+1) key[i] = m[{D[i],i}]; int r = 0; L.upd(0,MX-1,MOD); FOR(i,1,N+1) { while (L.qmin(0,MX-1) > 0 && r <= N) { r ++; if (r != N+1) { L.upd(key[r],key[r],D[r]-MOD); L.upd(key[r],MX-1,-T[r]); } } L.upd(key[i],key[i],MOD-D[i]); L.upd(key[i],MX-1,T[i]); ans[i] = r-1; } F0R(i,M) { int x,y; cin >> x >> y; cout << (ans[x] >= y) << "\n"; } } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...