Submission #739725

#TimeUsernameProblemLanguageResultExecution timeMemory
739725bgnbvnbvExamination (JOI19_examination)C++14
0 / 100
87 ms12852 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<ll,ll> #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=long long; const ll maxN=2e5; const ll inf=1e18; const ll mod=1e9+7; ll n,q; struct qq { ll s,t; bool operator<(const qq&o) { return s>o.s; } }x[maxN]; pli y[maxN],z[maxN]; ll bs(ll val) { ll low=1,high=n; while(low<=high) { ll mid=low+high>>1; if(x[mid].s<=val) high=mid-1; else low=mid+1; } return low; } struct qqq { ll c,l,r,id; bool operator<(const qqq&o) { return c<o.c; } }; vector<qqq>q1,q2; ll bit[maxN]; void update(ll i,ll v) { while(i<=n) { bit[i]+=v; i+=i&(-i); } } ll get(ll l,ll r) { l--; ll ans=0; while(r>0) { ans+=bit[r]; r-=r&(-r); } while(l>0) { ans-=bit[l]; l-=(l&(-l)); } return ans; } ll ans[maxN]; void solve() { cin >> n >> q; for(int i=1;i<=n;i++) cin >> x[i].s >> x[i].t; sort(x+1,x+n+1); for(int i=1;i<=n;i++) { y[i]={x[i].t,i}; z[i]={x[i].t+x[i].s,i}; } sort(y+1,y+n+1); sort(z+1,z+n+1); for(int i=1;i<=q;i++) { ll a,b,c; cin >> a >> b >> c; ll r=bs(a-1); r--; ll l=bs(c-b); if(l<=r) { q1.pb({c,l,r,i}); } l--; l=min(l,r); if(1<=l) { q2.pb({b,1,l,i}); } } sort(q1.begin(),q1.end()); ll j=n; for(int i=(int)q1.size()-1;i>=0;i--) { while(j>0&&z[j].fi>=q1[i].c) { update(z[j].se,1); j--; } ans[q1[i].id]+=get(q1[i].l,q1[i].r); } for(int i=n;i>j;i--) { update(z[i].se,-1); } j=n; for(int i=(int)q2.size()-1;i>=0;i--) { while(j>0&&y[j].fi>=q2[i].c) { update(y[j].se,1); j--; } ans[q2[i].id]+=get(q2[i].l,q2[i].r); } for(int i=1;i<=q;i++) cout << ans[i] <<'\n'; } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }

Compilation message (stderr)

examination.cpp: In function 'll bs(ll)':
examination.cpp:28:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         ll mid=low+high>>1;
      |                ~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...