Submission #497648

#TimeUsernameProblemLanguageResultExecution timeMemory
497648penguin133Examination (JOI19_examination)C++17
100 / 100
711 ms242156 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second int n,q; pair<int, pair<int, pair<int, int> > > Q[100005]; pair<int, pair<int, int> > X[100005]; int ans[100005]; struct node{ int s,e,m,val,val2; node *l, *r; node(int _s, int _e){ s = _s, e = _e, m = (s + e)/2; l = r = nullptr; } void mc(){ if(l != nullptr)return; if(s != e){ l = new node(s,m); r = new node(m+1,e); } } void up1(int p, int v){ if(s == e)val += v; else{ mc(); if(p <= m)l->up1(p,v); else r->up1(p,v); val = l->val + r->val; } } void up2(int p, int v){ if(s == e)val2 += v; else{ mc(); if(p <= m)l->up2(p,v); else r->up2(p,v); val2 = l->val2 + r->val2; } } int q1(int a, int b){ if(l == nullptr)return val; else if(s == a && b == e)return val; else if(b <= m)return l->q1(a,b); else if(a > m)return r->q1(a,b); else return l->q1(a,m) + r->q1(m+1, b); } int q2(int a,int b){ if(l == nullptr)return val2; else if(s == a && b == e)return val2; else if(b <= m)return l->q2(a,b); else if(a > m)return r->q2(a,b); else return l->q2(a,m) + r->q2(m+1, b); } }*root; int main(){ //ios::sync_with_stdio(0);cin.tie(0); cin >> n >> q; for(int i=1;i<=n;i++)cin >> X[i].s.f >> X[i].s.s, X[i].f = X[i].s.f + X[i].s.s; for(int i=1;i<=q;i++)cin >> Q[i].s.f >> Q[i].s.s.f >> Q[i].f, Q[i].f = max(Q[i]. f, Q[i].s.f + Q[i].s.s.f), Q[i].s.s.s = i; sort(Q+1, Q+q+1); sort(X+1, X+n+1); root = new node(0, 1e9 + 100); int in = n, ans2 = 0; for(int i=q;i>=1;i--){ int w = Q[i].f, x = Q[i].s.f, y = Q[i].s.s.f, z = Q[i].s.s.s; //cout << w << " " << x << '\n'; while(in >= 1 && X[in].f >= w){ ans2++; root->up1(X[in].s.f, 1); root->up2(X[in].s.s, 1); in--; } ans[z] =ans2; if(x > 0)ans[z] -= root->q1(0,x-1); if(y > 0)ans[z] -= root->q2(0,y-1); } for(int i=1;i<=q;i++)cout << ans[i] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...