제출 #226652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226652		nafis_shifat	Examination (JOI19_examination)	C++14	100 / 100	425 ms	19064 KiB

examination

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=2e5+4;

struct BIT
{
	
	int bit[mxn]={};

	void update(int i,int v)
	{
		for(;i>0;i-=i&-i)
		{
			bit[i]+=v;
		}
	}

	int query(int i)
	{
		ll s=0;
		for(;i<=mxn;i+=i&-i)
		{
			s+=bit[i];
		}
		return s;
	}
}bt;

struct score{
	int a,b,tot;
	int type;
	int id;
	score(int _a,int _b,int tt,int tp,int i):a(_a),b(_b),tot(tt),type(tp),id(i){};
};


int ans[mxn]={};
vector<score> sc;
void solve(int l ,int r)
{
	if(l==r)return;


	int mid=l+r>>1;

	vector<score> tmp;

	for(int i=l;i<=mid;i++)
	{
		if(sc[i].type==0)tmp.push_back(sc[i]);
	}

	for(int i=mid+1;i<=r;i++)
		if(sc[i].type==1)tmp.push_back(sc[i]);

	sort(tmp.begin(),tmp.end(),[](score a,score b)
	{
		if(a.a==b.a)return a.type<b.type;
		return a.a>b.a;

	});

	for(int i=0;i<tmp.size();i++)
	{
		if(tmp[i].type==0)
		{
			bt.update(tmp[i].b,1);
		}
		else
		{
			ans[tmp[i].id]+=bt.query(tmp[i].b);
		}
	}

	for(int i=0;i<tmp.size();i++)
		if(tmp[i].type==0)bt.update(tmp[i].b,-1);

	solve(l,mid);
	solve(mid+1,r);


}
int main()
{
	int n,q;
	cin>>n>>q;
	vector<int> A,B;

	

	for(int i=0;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		sc.push_back(score(a,b,a+b,0,-1));
		A.push_back(a);
		B.push_back(b);
	}

	for(int i=0;i<q;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		sc.push_back(score(a,b,c,1,i));
	}






	sort(A.begin(),A.end());
	sort(B.begin(),B.end());
	sort(sc.begin(),sc.end(),[](score a,score b)
	{
		return (a.tot==b.tot)?a.type<b.type : a.tot>b.tot;
	});


	A.erase(unique(A.begin(),A.end()),A.end());
	B.erase(unique(B.begin(),B.end()),B.end());

	for(int i=0;i<sc.size();i++)
	{
		sc[i].a=lower_bound(A.begin(),A.end(),sc[i].a)-A.begin()+1;
		sc[i].b=lower_bound(B.begin(),B.end(),sc[i].b)-B.begin()+1;
	}
	solve(0,sc.size()-1);

	for(int i=0;i<q;i++)
	{
		printf("%d\n",ans[i]);
	}






	return 0;
}

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

examination.cpp: In function 'void solve(int, int)':
examination.cpp:46:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
examination.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++)
              ~^~~~~~~~~~~
examination.cpp:77:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++)
              ~^~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:125:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<sc.size();i++)
              ~^~~~~~~~~~
examination.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~
examination.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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