제출 #121946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121946		MvC	Examination (JOI19_examination)	C++11	2 / 100	3044 ms	381124 KiB

examination

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
//#include "rail.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=6e5+50;
const int mod=1e9+7;
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,q,i,j,k,a[nmax],b[nmax],c[nmax],x[nmax],y[nmax],rs[nmax],nr,sm[nmax],s;
order_set st[4*nmax];
vector<int>qr[nmax];
vector<pair<int,pair<int,int> > >qrr[nmax],vc;
pair<int,pair<int,int> >p;
void upd(int x,int l,int r,int p,int v)
{
	st[x].in(mkp(v,nr));
	if(l==r)return;
	int mid=(l+r)/2;
	if(p<=mid)upd(2*x,l,mid,p,v);
	else upd(2*x+1,mid+1,r,p,v);
}
int qry(int x,int l,int r,int tl,int tr,int v)
{
	if(l>tr || r<tl)return 0;
	if(l>=tl && r<=tr)
	{
		v--;
		auto it=st[x].upper_bound(mkp(v,1e6));
		if(it==st[x].end())return 0;
		pair<int,int> y=*it;
		int z=(int)st[x].size()-st[x].order_of_key(y);
		return z;
	}
	int mid=(l+r)/2;
	return qry(2*x,l,mid,tl,tr,v)+qry(2*x+1,mid+1,r,tl,tr,v);
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>q;
	for(i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
		vc.pb(mkp(x[i],mkp(0,i)));
		vc.pb(mkp(y[i],mkp(1,i)));
		vc.pb(mkp(x[i]+y[i],mkp(2,i)));
	}
	for(i=1;i<=q;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
		vc.pb(mkp(a[i],mkp(3,i)));
		vc.pb(mkp(b[i],mkp(4,i)));
		vc.pb(mkp(c[i],mkp(5,i)));
	}
	sort(vc.begin(),vc.end());
	for(i=0;i<vc.size();)
	{
		k++;
		for(j=i;j<vc.size();j++)
		{
			if(vc[j].fr!=vc[i].fr)break;
			if(vc[j].sc.fr==2)sm[vc[j].sc.sc]=k;
			else if(vc[j].sc.fr==1)y[vc[j].sc.sc]=k;
			else if(vc[j].sc.fr==0)x[vc[j].sc.sc]=k;
			else if(vc[j].sc.fr==3)a[vc[j].sc.sc]=k;
			else if(vc[j].sc.fr==4)b[vc[j].sc.sc]=k;
			else if(vc[j].sc.fr==5)c[vc[j].sc.sc]=k;
		}
		i=j;
	}
	for(i=1;i<=n;i++)
	{
		qr[sm[i]].pb(i);
		//cout<<x[i]<<" "<<y[i]<<" "<<sm[i]<<endl;
	}
	for(i=1;i<=q;i++)
	{
		qrr[c[i]].pb(mkp(i,mkp(a[i],b[i])));
	}
	for(i=k;i>=1;i--)
	{
		for(j=0;j<qr[i].size();j++)
		{
			s=qr[i][j];
			nr++;
			upd(1,1,k,x[s],y[s]);
		}
		for(j=0;j<qrr[i].size();j++)
		{
			p=qrr[i][j];
			rs[p.fr]=qry(1,1,k,p.sc.fr,k,p.sc.sc);
		}
	}
	for(i=1;i<=q;i++)cout<<rs[i]<<'\n';
    return 0;
}

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

examination.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
examination.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
examination.cpp: In function 'int main()':
examination.cpp:76:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vc.size();)
          ~^~~~~~~~~~
examination.cpp:79:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=i;j<vc.size();j++)
           ~^~~~~~~~~~
examination.cpp:102:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<qr[i].size();j++)
           ~^~~~~~~~~~~~~
examination.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<qrr[i].size();j++)
           ~^~~~~~~~~~~~~~

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