Submission #490106

#	Time	Username	Problem	Language	Result	Execution time	Memory
490106		cfalas	Examination (JOI19_examination)	C++17	0 / 100	330 ms	3452 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FORi(i,a,b) for(ll i=((ll)a);i<(ll)b;i++)
#define FOR(i,n) FORi(i,0,n)
#define INF 120
#define MID ((l+r)/2)
typedef pair<int, int> ii;
#define F first
#define S second
struct seg{
	seg* L=NULL, *R=NULL;
	int val=0;
	void update(int x, int l=0, int r=INF){
		if(l==r && l==x) val++;
		else if(l==r) return;
		else{
			if(x<=MID){
				if(!L) L = new seg;
				L->update(x,l,MID);
			}
			else{
				if(!R) R = new seg;
				R->update(x,MID+1,r);
			}
			val = 0;
			if(L) val+=L->val;
			if(R) val+=R->val;
		}
	}
	int query(int rl, int rr, int l=0, int r=INF){
		if(rl<=l && r<=rr) return val;
		else if(rr<l || r<rl) return 0;
		else{
			int ans=0;
			if(L) ans+=L->query(rl,rr,l,MID);
			if(R) ans+=R->query(rl,rr,MID+1,r);
			return ans;
		}
	}
};

struct seg2{
	seg2* L=NULL, *R=NULL;
	seg val;
	void update(ii x, int l=0, int r=INF){
		if(l==r && l==x.F) val.update(x.S);
		else if(l==r) return;
		else{
			if(x.F<=MID){
				if(!L) L = new seg2;
				L->update(x,l,MID);
			}
			else{
				if(!R) R = new seg2;
				R->update(x,MID+1,r);
			}
			val.update(x.S);
		}
	}
	int query(ii rl, ii rr, int l=0, int r=INF){
		if(rl.F<=l && r<=rr.F) return val.query(rl.S, rr.S);
		else if(rr.F<l || r<rl.F) return 0;
		else{
			int ans=0;
			if(L) ans+=L->query(rl,rr,l,MID);
			if(R) ans+=R->query(rl,rr,MID+1,r);
			return ans;
		}
	}
};
struct seg3{
	seg3* L=NULL, *R=NULL;
	seg2 val;
	void update(pair<ii,int> x, int l=0, int r=2*INF){
		if(l==r && l==x.S) val.update(x.F);
		else if(l==r) return;
		else{
			if(x.S<=MID){
				if(!L) L = new seg3;
				L->update(x,l,MID);
			}
			else{
				if(!R) R = new seg3;
				R->update(x,MID+1,r);
			}
			val.update(x.F);
		}
	}
	int query(pair<ii,int> rl, pair<ii,int> rr, int l=0, int r=2*INF){
		if(rl.S<=l && r<=rr.S) return val.query(rl.F, rr.F);
		else if(rr.S<l || r<rl.S) return 0;
		else{
			int ans=0;
			if(L) ans+=L->query(rl,rr,l,MID);
			if(R) ans+=R->query(rl,rr,MID+1,r);
			return ans;
		}
	}
};

int main(){
	int n, q;
	cin>>n>>q;
	seg3 s;
	FOR(i,n){
		int a, b;
		cin>>a>>b;
		s.update({{a,b}, a+b});
	}
	while(q--){
		int a, b, c;
		cin>>a>>b>>c;
		cout<<s.query({{a,b},c}, {{INF, INF}, 2*INF})<<endl;
	}
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57