oj.uz

답안 #219046

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
219046 2020-04-03T13:09:22 Z kshitij_sodani Examination (JOI19_examination) C++17
0 / 100
 1097 ms 1048576 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
bool cmp(pair<pair<llo,llo>,pair<llo,int>> ac,pair<pair<llo,llo>,pair<llo,int>> cc){
	return ac.b.a<=cc.b.a;
}
bool cmp2(pair<pair<llo,llo>,int> ac,pair<pair<llo,llo>,int> cc){
	return ac.a.a+ac.a.b<=cc.a.a+cc.a.b;
}
bool cmp3(pair<pair<llo,llo>,int> ac,pair<pair<llo,llo>,int> cc){
	return ac.a.a<=cc.a.a;
}
vector<int> tree[400001];
vector<pair<llo,int>> ss[400001];
vector<int> indd[400001];
pair<llo,llo> bb[100001];
void u(int no,int i,int j){
	while(i<=tree[no].size()){
		tree[no][i]+=j;
		i+=(i&-i);
	}
}
int st(int no,int i){
	int tot=0;
	while(i>0){
		tot+=tree[no][i];
		i-=(i&-i);
	}
	return tot;
}
void build(int no,int l,int r){
	for(int i=l;i<=r+1;i++){
		tree[no].pb(0);
		indd[no].pb(0);
	}
	if(r>l){
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		int ind=0;
		int ind2=0;
		int ind3=0;
		while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
			if(ss[no*2+1][ind].a<ss[no*2+2][ind2].a){
				ss[no].pb(ss[no*2+1][ind]);
				indd[no][ss[no*2+1][ind].b-l]=ind3;
				ind+=1;
				ind3+=1;
			}
			else{
				ss[no].pb(ss[no*2+2][ind2]);
				indd[no][ss[no*2+2][ind2].b-l]=ind3;
				ind2+=1;
				ind3+=1;
			}
		}
		while(ind<ss[no*2+1].size() ){
			ss[no].pb(ss[no*2+1][ind]);
			indd[no][ss[no*2+1][ind].b-l]=ind3;
			ind+=1;
			ind3+=1;
		}
		while(ind2<ss[no*2+2].size()){
			ss[no].pb(ss[no*2+2][ind2]);
			indd[no][ss[no*2+2][ind2].b-l]=ind3;
			ind2+=1;
			ind3+=1;
		}
	}
	else{
		ss[no].pb({bb[l].b,l});
	}
}
void update(int no,int l,int r,int ind){
	if(ind<l or ind>r){
		return;
	}
	u(no,indd[no][ind-l]+1,1);
	if(r>l){
		int mid=(l+r)/2;
		update(no*2+1,l,mid,ind);
		update(no*2+2,mid+1,r,ind);
	}
}
llo kk;
llo cp;
int query(int no,int l,int r){
	if(bb[r].a<kk){
		return 0;
	}
	if(bb[l].a>=kk){
		if(ss[no][r-l].a<cp){
			return 0;
		}
		int low=0;
		int high=r-l;
		while(low<high-1){
			int mid=(low+high)/2;
			if(ss[no][mid].a>=cp){
				high=mid;
			}
			else{
				low=mid+1;
			}
		}
		int dd=high;
		if(ss[no][low].a>=cp){
			dd=low;
		}
		int xx=st(no,r-l+1);
		if(dd>0){
			xx-=st(no,dd);
		}
		return xx;
	}
	else{
		int mid=(l+r)/2;
		return query(no*2+1,l,mid)+query(no*2+2,mid+1,r);
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,q;
	cin>>n>>q;
	pair<pair<llo,llo>,int> aa[n];
	for(int i=0;i<n;i++){
		cin>>aa[i].a.a>>aa[i].a.b;
	}
	sort(aa,aa+n,cmp3);
	for(int i=0;i<n;i++){
		aa[i].b=i;
	}
	for(int i=0;i<n;i++){
		bb[i]=aa[i].a;
	}

	sort(aa,aa+n,cmp2);
	llo pp,bb,cc;
	vector<pair<pair<llo,llo>,pair<llo,int>>> qq;
	for(int i=0;i<q;i++){
		cin>>pp>>bb>>cc;
		qq.pb({{pp,bb},{cc,i}});
	}

	sort(qq.begin(),qq.end(),cmp);
	int pos=n-1;
	int ans[q];
	build(0,0,n-1);
//	cout<<33<<endl;

	for(int ii=q-1;ii>=0;ii--){
		llo ba=qq[ii].b.a;
		while(pos>=0){
			if(aa[pos].a.a+aa[pos].a.b>=ba){
				update(0,0,n-1,aa[pos].b);
			//	cout<<aa[pos].b<<" "<<ii<<endl;
				pos-=1;
			}
			else{
				break;
			}
		}
		kk=qq[ii].a.a;
		cp=qq[ii].a.b;
		int ans4=query(0,0,n-1);
		ans[qq[ii].b.b]=ans4;
	}
	for(int i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

Compilation message

examination.cpp: In function 'void u(int, int, int)':
examination.cpp:24:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<=tree[no].size()){
        ~^~~~~~~~~~~~~~~~~
examination.cpp: In function 'void build(int, int, int)':
examination.cpp:49:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
         ~~~^~~~~~~~~~~~~~~~~~
examination.cpp:49:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
                                   ~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:63:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<ss[no*2+1].size() ){
         ~~~^~~~~~~~~~~~~~~~~~
examination.cpp:69:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2<ss[no*2+2].size()){
         ~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 28544 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 21 ms 28544 KB Output is correct
4 Correct 21 ms 28544 KB Output is correct
5 Correct 21 ms 28544 KB Output is correct
6 Correct 21 ms 28544 KB Output is correct
7 Correct 34 ms 30464 KB Output is correct
8 Correct 32 ms 30464 KB Output is correct
9 Correct 35 ms 30464 KB Output is correct
10 Correct 32 ms 30464 KB Output is correct
11 Runtime error 1097 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 148 ms 73824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 148 ms 73824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 28544 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 21 ms 28544 KB Output is correct
4 Correct 21 ms 28544 KB Output is correct
5 Correct 21 ms 28544 KB Output is correct
6 Correct 21 ms 28544 KB Output is correct
7 Correct 34 ms 30464 KB Output is correct
8 Correct 32 ms 30464 KB Output is correct
9 Correct 35 ms 30464 KB Output is correct
10 Correct 32 ms 30464 KB Output is correct
11 Runtime error 1097 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -