제출 #497648

#제출 시각아이디문제언어결과실행 시간메모리
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...