oj.uz

Submission #771621

# Submission time Handle Problem Language Result Execution time Memory
771621 2023-07-03T07:29:36 Z Mohammad_Parsa Examination (JOI19_examination) C++17
2 / 100
 26 ms 12904 KB 
/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
#define ln (e-s+1)
#define md ((s+e)/2)
#define lc (2*id)
#define rc (2*id+1)
typedef long long ll;

const int N=1e5+7;
int n,q,a,b,c,mn[4*N],mx[4*N],ans;
pair<int,int>x[N];
vector<int>v[2][N];

void merge(int id,int f){
	int i=0,j=0;
	int sz1=v[f][lc].size(),sz2=v[f][rc].size();
	while(i!=sz1 || j!=sz2){
		if(i==sz1){
			v[f][id].pb(v[f][rc][j++]);
		}
		else if(j==sz2){
			v[f][id].pb(v[f][lc][i++]);
		}
		else{
			if(v[f][lc][i]>v[f][rc][j]){
				v[f][id].pb(v[f][rc][j++]);
			}
			else{
				v[f][id].pb(v[f][lc][i++]);
			}
		}
	}
}

void build(int id=1,int s=1,int e=n){
	if(ln==1){
		mn[id]=mx[id]=x[s].F;
		v[0][id].pb(x[s].F+x[s].S);
		v[1][id].pb(x[s].S);
		return;
	}
	build(lc,s,md);
	build(rc,md+1,e);
	merge(id,0);
	merge(id,1);
	mn[id]=mn[lc];
	mx[id]=mx[rc];
}

void get(int f,int l,int r,int id=1,int s=1,int e=n){
	if(mn[id]>r || l>mx[id])return;
	if(mn[id]>=l && mx[id]<=r){
		int L=-1,R=ln;
		//cout<<id<<endl;
		int w;
		if(f==0)w=c;
		else w=b;
		while(R-L>1){
			int m=(L+R)/2;
			if(v[f][id][m]<w)L=m;
			else R=m;
		}
		//cout<<L<<" "<<R<<endl;
		ans+=ln-R;
		return;
	}
	get(f,l,r,lc,s,md);
	get(f,l,r,rc,md+1,e);
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>x[i].F>>x[i].S;
	}
	sort(x+1,x+n+1);
	build();
	while(q--){
		cin>>a>>b>>c;
		ans=0;
		get(0,a,c-b);
		get(1,max(a,c-b+1),1e9+7);
		cout<<ans<<endl;
	}
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5032 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 7 ms 5964 KB Output is correct
8 Correct 8 ms 5944 KB Output is correct
9 Correct 7 ms 5960 KB Output is correct
10 Correct 10 ms 5812 KB Output is correct
11 Correct 5 ms 5844 KB Output is correct
12 Correct 6 ms 5816 KB Output is correct
13 Correct 6 ms 5844 KB Output is correct
14 Correct 8 ms 5880 KB Output is correct
15 Correct 8 ms 5912 KB Output is correct
16 Correct 6 ms 5808 KB Output is correct
17 Correct 8 ms 5844 KB Output is correct
18 Correct 4 ms 5844 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 12904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 12904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5032 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 7 ms 5964 KB Output is correct
8 Correct 8 ms 5944 KB Output is correct
9 Correct 7 ms 5960 KB Output is correct
10 Correct 10 ms 5812 KB Output is correct
11 Correct 5 ms 5844 KB Output is correct
12 Correct 6 ms 5816 KB Output is correct
13 Correct 6 ms 5844 KB Output is correct
14 Correct 8 ms 5880 KB Output is correct
15 Correct 8 ms 5912 KB Output is correct
16 Correct 6 ms 5808 KB Output is correct
17 Correct 8 ms 5844 KB Output is correct
18 Correct 4 ms 5844 KB Output is correct
19 Runtime error 26 ms 12904 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -