제출 #908750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
908750		StefanSebez	Examination (JOI19_examination)	C++14	2 / 100	3084 ms	11320 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int N=1e5+50;
int nc,root,lc[2*N],rc[2*N];
vector<int>nums[2*N];
void Update(int &c,int ss,int se,int qind,int qval)
{
	if(!c) c=++nc;
	if(ss==se)
	{
		nums[c].clear();
		nums[c].pb(qval);
		return;
	}
	int mid=(ss+se)/2;
	if(qind<=mid) Update(lc[c],ss,mid,qind,qval);
	else Update(rc[c],mid+1,se,qind,qval);
	nums[c].clear();
	for(int i=0,j=0;i<=nums[lc[c]].size();i++)
	{
		if(i==nums[lc[c]].size())
		{
			while(j<nums[rc[c]].size())
			{
				nums[c].pb(nums[rc[c]][j]);
				j++;
			}
			break;
		}
		while(j<nums[rc[c]].size() && nums[rc[c]][j]<=nums[lc[c]][i])
		{
			nums[c].pb(nums[rc[c]][j]);
			j++;
		}
		nums[c].pb(nums[lc[c]][i]);
	}
}
int Get(int &c,int ss,int se,int qs,int qe,int qval)
{
	if(qs>qe) return 0;
	if(qs<=ss && se<=qe)
	{
		int lb=lower_bound(nums[c].begin(),nums[c].end(),qval)-nums[c].begin();
		return nums[c].size()-lb;
	}
	else if(qe<ss || se<qs) return 0;
	int mid=(ss+se)/2;
	return Get(lc[c],ss,mid,qs,qe,qval)+Get(rc[c],mid+1,se,qs,qe,qval);
}
int main()
{
    int n,q;scanf("%i%i",&n,&q);
    pair<int,pair<int,int> >a[n+1];
    pair<int,int>b[n+1];
    int c[n+1];
    for(int i=1;i<=n;i++)
	{
		scanf("%i%i",&a[i].se.fi,&a[i].se.se);
		a[i].fi=a[i].se.fi+a[i].se.se;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		Update(root,1,n,i,a[i].se.se);
		b[i]={a[i].se.fi,i};
		c[i]=a[i].fi;
	}
	sort(b+1,b+n+1);
	int ind[n+1];
	for(int i=1;i<=n;i++) ind[i]=b[i].se;
	/*for(int i=1;i<=n;i++) printf("%i ",ind[i]);
	printf("\n");*/
	/*for(int i=1;i<=n;i++) printf("%i ",c[i]);
	printf("\n");*/
    pair<pair<int,int>,pair<int,int> > qy[q+1];
    for(int i=1;i<=q;i++)
	{
		scanf("%i%i%i",&qy[i].fi.fi,&qy[i].fi.se,&qy[i].se.fi);
		qy[i].se.se=i;
	}
	sort(qy+1,qy+q+1);
	int res[q+1];
    for(int i=1,j=1;i<=q;i++)
	{
		int X=qy[i].fi.fi,Y=qy[i].fi.se,Z=qy[i].se.fi;
		while(j<=n && X>a[ind[j]].se.fi)
		{
			Update(root,1,n,ind[j],-1);
			j++;
		}
		int lb=lower_bound(c+1,c+n+1,Z)-c;
		//printf("%i %i\n",lb,Z);
		int ans=Get(root,1,n,lb,n,Y);
		//printf("%i %i %i %i %i\n",X,Y,Z,lb,ans);
		res[qy[i].se.se]=ans;
	}
	for(int i=1;i<=q;i++) printf("%i\n",res[i]);
    return 0;
}

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

examination.cpp: In function 'void Update(int&, int, int, int, int)':
examination.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0,j=0;i<=nums[lc[c]].size();i++)
      |                  ~^~~~~~~~~~~~~~~~~~~~
examination.cpp:24:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   if(i==nums[lc[c]].size())
      |      ~^~~~~~~~~~~~~~~~~~~~
examination.cpp:26:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    while(j<nums[rc[c]].size())
      |          ~^~~~~~~~~~~~~~~~~~~
examination.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   while(j<nums[rc[c]].size() && nums[rc[c]][j]<=nums[lc[c]][i])
      |         ~^~~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     int n,q;scanf("%i%i",&n,&q);
      |             ~~~~~^~~~~~~~~~~~~~
examination.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%i%i",&a[i].se.fi,&a[i].se.se);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   scanf("%i%i%i",&qy[i].fi.fi,&qy[i].fi.se,&qy[i].se.fi);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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