oj.uz

답안 #490111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490111 2021-11-25T18:06:32 Z cfalas Examination (JOI19_examination) C++17
0 / 100
 3000 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;
	int pos=-1;

	void push(int l, int r){
		if(pos!=-1){
			if(pos<=MID){
				L = new seg;
				L->val = 1;
				L->pos = pos;
			}
			else{
				R = new seg;
				R->val = 1;
				R->pos = pos;
			}
			pos = -1;
		}
	}

	void update(int x, int l=0, int r=INF){
		if(l==r && l==x) val++;
		else if(l==r) return;
		else{
			if(!L && !R && pos==-1){
				pos = x;
				val++;
				return;
			}
			push(l,r);
			assert(L || R);
			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{
			push(l,r);
			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;
	int pos=-1;

	void push(int l, int r){
		if(pos!=-1){
			if(pos<=MID){
				L = new seg2;
				L->val = val;
				L->pos = pos;
			}
			else{
				R = new seg2;
				R->val = val;
				R->pos = pos;
			}
			pos = -1;
		}
	}

	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(!L && !R && pos==-1){
				val.update(x.S);
				pos = x.F;
				return;
			}
			push(l,r);
			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{
			push(l,r);
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 3 ms 1740 KB Output is correct
3 Correct 3 ms 1868 KB Output is correct
4 Runtime error 581 ms 1048580 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3159 ms 893804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3159 ms 893804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 3 ms 1740 KB Output is correct
3 Correct 3 ms 1868 KB Output is correct
4 Runtime error 581 ms 1048580 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -