This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |