Submission #219043

#	Time	Username	Problem	Language	Result	Execution time	Memory
219043		kshitij_sodani	Examination (JOI19_examination)	C++17	0 / 100	1145 ms	1048580 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> cc){
	return ac.a.a+ac.a.b<=cc.a.a+cc.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 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+1;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;
	cin>>n>>q;
	pair<pair<llo,llo>,llo> aa[n];
	for(llo i=0;i<n;i++){
		cin>>aa[i].a.a>>aa[i].a.b;
	}
	sort(aa,aa+n,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,aa+n,cmp2);
	llo pp,bb,cc;
	vector<pair<pair<llo,llo>,pair<llo,llo>>> qq;
	for(llo i=0;i<q;i++){
		cin>>pp>>bb>>cc;
		qq.pb({{pp,bb},{cc,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;
}

Compilation message (stderr)

examination.cpp: In function 'void u(llo, llo, llo)':
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(llo, llo, llo)':
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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57