제출 #117476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117476		faustaadp	Examination (JOI19_examination)	C++17	100 / 100	2538 ms	270236 KiB

examination

#include<bits/stdc++.h>
typedef long long ll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
int n,q,a[101010],b[101010],ta,tb,tc,i,jaw[101010],j,te,KA,KB;
vector<pair<pair<int,int>,int> > isi[101010];
pair<int,int> A[101010];
int ki[29404040];
int ka[29404040];
int ST[29404040];
int RU[804040];
int tam[3][101010];
vector<int> za,zb;
unordered_map<int,int> mea,meb;
void upd2(int aa,int bb,int cc,int ee)
{
	if(aa==bb)
		ST[ee]++;
	else
	{
		int ce=(aa+bb)/2;
		if(cc<=ce)
		{
			if(!ki[ee])ki[ee]=++te;
			upd2(aa,ce,cc,ki[ee]);
		}
		else
		{
			if(!ka[ee])ka[ee]=++te;
			upd2(ce+1,bb,cc,ka[ee]);
		}
		ST[ee]=ST[ki[ee]]+ST[ka[ee]];
	}
}
void upd(int aa,int bb,int cc,int dd,int ee)
{
	if(RU[ee]==0)
		RU[ee]=++te;
	upd2(1,KB,KB-dd,RU[ee]);
	if(aa<bb)
	{
		int ce=(aa+bb)/2;
		if(cc<=ce)
			upd(aa,ce,cc,dd,ee*2);
		else
			upd(ce+1,bb,cc,dd,ee*2+1);
	}
}
int que2(int aa,int bb,int cc,int dd,int ee)
{
	if(bb<cc||dd<aa||ee==0)
		return 0;
	else
	if(cc<=aa&&bb<=dd)
		return ST[ee];
	else
	{
		int ce=(aa+bb)/2;
		return que2(aa,ce,cc,dd,ki[ee])+que2(ce+1,bb,cc,dd,ka[ee]);
	}
}
int que(int aa,int bb,int cc,int dd,int ee,int ff)
{
//	cout<<aa<<" "<<bb<<" "<<cc<<" "<<dd<<" "<<ee<<" "<<ff<<"\n";
	if(bb<cc||dd<aa)
		return 0;
	else
	if(cc<=aa&&bb<=dd)
	{
		//cout<<aa<<" "<<bb<<"_\n";
		return que2(1,KB,1,KB-ff,RU[ee]);
	}
	else
	{
		int ce=(aa+bb)/2;
		return que(aa,ce,cc,dd,ee*2,ff)+que(ce+1,bb,cc,dd,ee*2+1,ff);
	}
}
int main()
{
//	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		za.pb(a[i]);
		zb.pb(b[i]);
		A[i]=mp(a[i]+b[i],i);
	}
	sort(A+1,A+1+n);
	for(i=1;i<=q;i++)
	{
		cin>>tam[0][i]>>tam[1][i]>>tam[2][i];
		za.pb(tam[0][i]);
		zb.pb(tam[1][i]);
	}
	sort(za.begin(),za.end());
	sort(zb.begin(),zb.end());
	KA=1;
	KB=1;
	for(i=0;i<za.size();i++)
	{
		if(i==0||za[i]!=za[i-1])
		{
			mea[za[i]]=KA;
			KA++;
		}
	}
	for(i=0;i<zb.size();i++)
	{
		if(i==0||zb[i]!=zb[i-1])
		{
			meb[zb[i]]=KB;
			KB++;
		}
	}
	for(i=1;i<=q;i++)
	{
		ta=tam[0][i];
		tb=tam[1][i];
		tc=tam[2][i];
		int L=1,R=n,C,hz=0,ki=n+1;
		while(L<=R)
		{	
			C=(L+R)/2;
			if(A[C].fi>=tc)
			{
				ki=C;
				R=C-1;
			}
			else
				L=C+1;
		}
		isi[ki].pb(mp(mp(ta,tb),i));
		//cout<<ki<<"\n";
		// if((n<=3000&&q<=3000))
		// {		
		// 	for(j=1;j<=n;j++)
		// 		if(a[j]>=ta&&b[j]>=tb&&(a[j]+b[j])>=tc)
		//  			hz++;
		// 	cout<<hz<<"\n";
		// }
	}
	// if((n<=3000&&q<=3000))return 0;
	//K=za.size()+3;
	KA++;
	KB++;
	KA=max(KA,KB);
	KB=max(KA,KB);
	for(i=n;i>=1;i--)
	{
	//	cout<<i<<" "<<a[A[i].se]<<" "<<b[A[i].se]<<"\n";
	//	cout<<mea[a[A[i].se]]<<" "<<meb[b[A[i].se]]<<"\n";
		upd(1,KA,mea[a[A[i].se]],meb[b[A[i].se]],1);
		//continue;
		for(j=0;j<isi[i].size();j++)
		{
	//		cout<<mea[isi[i][j].fi.fi]<<" "<<meb[isi[i][j].fi.se]<<"\n";
		//	cout<<i<<"\n";
			jaw[isi[i][j].se]=que(1,KA,mea[isi[i][j].fi.fi],KA,1,meb[isi[i][j].fi.se]);
		}
	}
	for(i=1;i<=q;i++)
		cout<<jaw[i]<<"\n";
}

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

examination.cpp: In function 'int main()':
examination.cpp:104:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<za.size();i++)
          ~^~~~~~~~~~
examination.cpp:112:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<zb.size();i++)
          ~^~~~~~~~~~
examination.cpp:125:17: warning: unused variable 'hz' [-Wunused-variable]
   int L=1,R=n,C,hz=0,ki=n+1;
                 ^~
examination.cpp:159:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<isi[i].size();j++)
           ~^~~~~~~~~~~~~~

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