제출 #126812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126812		mohammedehab2002	Examination (JOI19_examination)	C++11	100 / 100	2765 ms	163704 KiB

examination

#include <iostream>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <map>
using namespace std;
using namespace __gnu_pbds;
map<int,int> comp;
pair<int,int> arr[100005];
int x[100005],y[100005],z[100005],p[100005],ans[100005];
bool cmp(int a,int b)
{
	return x[a]>x[b];
}
tree<int,null_type,greater_equal<int>,rb_tree_tag,tree_order_statistics_node_update> s[800005];
void update(int node,int st,int en,int idx,int val)
{
	s[node].insert(val);
	if (st!=en)
	{
		int mid=(st+en)/2;
		if (st<=idx && idx<=mid)
		update(2*node,st,mid,idx,val);
		else
		update(2*node+1,mid+1,en,idx,val);
	}
}
int query(int node,int st,int en,int l,int r,int val)
{
	if (en<l || st>r || r<l)
	return 0;
	if (l<=st && en<=r)
	return s[node].order_of_key(val-1);
	int mid=(st+en)/2;
	return query(2*node,st,mid,l,r,val)+query(2*node+1,mid+1,en,l,r,val);
}
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	for (int i=0;i<n;i++)
	{
		scanf("%d%d",&arr[i].first,&arr[i].second);
		comp[arr[i].second];
	}
	for (int i=0;i<q;i++)
	{
		scanf("%d%d%d",&x[i],&y[i],&z[i]);
		p[i]=i;
		comp[y[i]];
	}
	int cur=0;
	for (auto &l:comp)
	l.second=cur++;
	sort(p,p+q,cmp);
	sort(arr,arr+n);
	int idx=n-1;
	for (int i=0;i<q;i++)
	{
		while (idx>=0 && arr[idx].first>=x[p[i]])
		{
			update(1,0,cur-1,comp[arr[idx].second],arr[idx].first+arr[idx].second);
			idx--;
		}
		ans[p[i]]=query(1,0,cur-1,comp[y[p[i]]],cur-1,z[p[i]]);
	}
	for (int i=0;i<q;i++)
	printf("%d\n",ans[i]);
}

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

examination.cpp: In function 'int main()':
examination.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~
examination.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&arr[i].first,&arr[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x[i],&y[i],&z[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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