Submission #363917

#TimeUsernameProblemLanguageResultExecution timeMemory
363917ogibogi2004Cambridge (info1cup18_cambridge)C++14
100 / 100
239 ms13156 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long const ll MAXN=1e5+6; const ll INF=2e9; struct SegmentTree { ll node[4*MAXN]; ll lazy[4*MAXN]; bool lz[4*MAXN]; void init() { memset(lz,0,sizeof(lz)); memset(lazy,0,sizeof(lazy)); memset(node,0,sizeof(node)); } ll merge(ll n1,ll n2) { return max(n1,n2); } void push(ll idx,ll l,ll r) { if(lz[idx]==0)return; node[idx]+=lazy[idx]; if(l!=r) { lz[idx*2]=1; lz[idx*2+1]=1; lazy[idx*2]+=lazy[idx]; lazy[idx*2+1]+=lazy[idx]; } lazy[idx]=0; lz[idx]=0; } void update(ll idx,ll l,ll r,ll ql,ll qr,ll val) { push(idx,l,r); if(l>qr||r<ql||l>r)return; if(l>=ql&&r<=qr) { lz[idx]=1; lazy[idx]+=val; push(idx,l,r); return; } ll mid=(l+r)/2; update(idx*2,l,mid,ql,qr,val); update(idx*2+1,mid+1,r,ql,qr,val); node[idx]=merge(node[idx*2],node[idx*2+1]); } ll query(ll idx,ll l,ll r,ll ql,ll qr) { push(idx,l,r); if(l>qr||r<ql||l>r)return -INF; if(l>=ql&&r<=qr)return node[idx]; ll mid=(l+r)/2; return merge(query(idx*2,l,mid,ql,qr),query(idx*2+1,mid+1,r,ql,qr)); } }tree; ll n,m; ll t[MAXN],d[MAXN]; ll maxright[MAXN]; ll where[MAXN]; void add(ll idx) { tree.update(1,1,n,where[idx],where[idx],INF-d[idx]); tree.update(1,1,n,where[idx],n,t[idx]); } void remove(ll idx) { tree.update(1,1,n,where[idx],where[idx],-INF+d[idx]); tree.update(1,1,n,where[idx],n,-t[idx]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; vector<pair<ll,ll> >v; for(ll i=1;i<=n;i++) { cin>>t[i]>>d[i]; v.push_back({d[i],i}); } sort(v.begin(),v.end()); for(ll i=0;i<v.size();++i) { where[v[i].second]=i+1; } ll r=0; //tree.init(); //cout<<tree.query(1,1,n,1,n)<<endl; tree.update(1,1,n,1,n,-INF); //cout<<tree.query(1,1,n,1,n)<<endl; for(ll l=1;l<=n;l++) { while(r<=n&&tree.query(1,1,n,1,n)<0) { r++; if(r<=n)add(r); } remove(l); maxright[l]=r-1; } //for(ll i=1;i<=n;i++)cout<<maxright[i]<<" "; //cout<<endl; for(ll i=0;i<m;i++) { ll ez,dp; cin>>ez>>dp; if(maxright[ez]>=dp) { cout<<"1\n"; } else cout<<"0\n"; } return 0; }

Compilation message (stderr)

cambridge.cpp: In function 'int main()':
cambridge.cpp:87:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(ll i=0;i<v.size();++i)
      |             ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...