제출 #219055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219055		kshitij_sodani	Examination (JOI19_examination)	C++17	100 / 100	957 ms	128084 KiB

examination

#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,llo>> ac,pair<pair<llo,llo>,pair<llo,llo>> cc){
	return ac.b.a<cc.b.a;
}
bool cmp2(pair<pair<llo,llo>,llo> ac,pair<pair<llo,llo>,llo> cd){
	return ac.a.a+ac.a.b<cd.a.a+cd.a.b;
}
bool cmp3(pair<pair<llo,llo>,llo> ac,pair<pair<llo,llo>,llo> cc){
	return ac.a.a<cc.a.a;
}
vector<llo> tree[400001];
vector<pair<llo,llo>> ss[400001];
vector<llo> indd[400001];
pair<llo,llo> bb[100001];
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
//	freopen((name+".out").c_str(),"w",stdout);
}
void u(llo no,llo i,llo j){
	while(i<tree[no].size()){
		tree[no][i]+=j;
		i+=(i&-i);
	}
}
llo st(llo no,llo i){
	llo tot=0;
	while(i>0){
		tot+=tree[no][i];
		i-=(i&-i);
	}
	return tot;
}
void build(llo no,llo l,llo r){
	for(llo i=l;i<=r+2;i++){
		tree[no].pb(0);
		indd[no].pb(0);
	}
	if(r>l){
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		llo ind=0;
		llo ind2=0;
		llo 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(llo no,llo l,llo r,llo ind){
	if(ind<l or ind>r){
		return;
	}
	u(no,indd[no][ind-l]+1,1);
	if(r>l){
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,ind);
		update(no*2+2,mid+1,r,ind);
	}
}
llo kk;
llo cp;
llo query(llo no,llo l,llo r){
	if(bb[r].a<kk){
		return 0;
	}

	if(bb[l].a>=kk){
		if(ss[no][r-l].a<cp){
			return 0;
		}
		llo low=0;
		llo high=r-l;
		while(low<high-1){
			llo mid=(low+high)/2;
			if(ss[no][mid].a>=cp){
				high=mid;
			}
			else{
				low=mid+1;
			}
		}
		llo dd=high;
		if(ss[no][low].a>=cp){
			dd=low;
		}
		llo xx=st(no,r-l+1);
		if(dd>0){
			xx-=st(no,dd);
		}
		return xx;
	}
	else{
		llo 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);
	llo n,q;
	//setIO("11");
	cin>>n>>q;
	vector<pair<pair<llo,llo>,llo>> aa;
	llo mm,nn;
	for(llo i=0;i<n;i++){
		cin>>mm>>nn;
		aa.pb({{mm,nn},0});
	}
	sort(aa.begin(),aa.end(),cmp3);
	for(llo i=0;i<n;i++){
		aa[i].b=i;
	}
	for(llo i=0;i<n;i++){
		bb[i]=aa[i].a;
	}

	sort(aa.begin(),aa.end(),cmp2);

	

	llo pp,bc,cd;
	vector<pair<pair<llo,llo>,pair<llo,llo>>> qq;
	for(llo i=0;i<q;i++){
		cin>>pp>>bc>>cd;
		qq.pb({{pp,bc},{cd,i}});
	}
	sort(qq.begin(),qq.end(),cmp);
	llo pos=n-1;
	llo ans[q];
	build(0,0,n-1);
//	cout<<33<<endl;

	for(llo 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;
		llo ans4=query(0,0,n-1);
		ans[qq[ii].b.b]=ans4;
	}
	for(llo i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'void u(llo, llo, llo)':
examination.cpp:29:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<tree[no].size()){
        ~^~~~~~~~~~~~~~~~
examination.cpp: In function 'void build(llo, llo, llo)':
examination.cpp:54: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:54: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:68:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<ss[no*2+1].size() ){
         ~~~^~~~~~~~~~~~~~~~~~
examination.cpp:74:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2<ss[no*2+2].size()){
         ~~~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'void setIO(std::__cxx11::string)':
examination.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((name+".in").c_str(),"r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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