oj.uz

Submission #490107

# Submission time Handle Problem Language Result Execution time Memory
490107 2021-11-25T17:48:38 Z cfalas Examination (JOI19_examination) C++17
0 / 100
 1537 ms 1048580 KB 
#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 1e9
#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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4556 KB Output is correct
3 Correct 6 ms 4556 KB Output is correct
4 Runtime error 743 ms 1048580 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1537 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1537 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4556 KB Output is correct
3 Correct 6 ms 4556 KB Output is correct
4 Runtime error 743 ms 1048580 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -