Submission #1190433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190433		boclobanchat	Examination (JOI19_examination)	C++20	0 / 100	291 ms	7608 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=1e5+5;
const int sqr=320;
const int INF=1e9;
struct query { int l,r,u,pos; };
bool comp(query a,query b) { if(a.l/sqr==b.l/sqr) return a.r<b.r;return a.l<b.l; }
int cnt[MAXN],block[MAXN/sqr+5],cc[MAXN],va[MAXN],vb[MAXN],vc[MAXN],ans[MAXN],F[MAXN];
ii A[MAXN],B[MAXN],C[MAXN];
query Q[MAXN];
void update(int i,int val)
{
	int a=(i-1)/sqr;
	block[a]+=val-cnt[i],cnt[i]=val;
}
int get(int i)
{
	int ans=0;
	while(i%sqr) ans+=cnt[i--];
	i=(i-1+sqr)/sqr-1;
	while(i>0) ans+=block[--i];
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>A[i].fi>>A[i].se;
		A[i]={INF-A[i].fi,INF-A[i].se};
		va[i]=A[i].fi,vb[i]=A[i].se,vc[i]=A[i].fi+A[i].se-INF;
	}
	sort(va+1,va+n+1);
	sort(vb+1,vb+n+1);
	sort(vc+1,vc+n+1);
	for(int i=1;i<=n;i++)
	{
		int a=lower_bound(va+1,va+n+1,A[i].fi)-va;
		int b=lower_bound(vb+1,vb+n+1,A[i].se)-vb;
		int c=lower_bound(vc+1,vc+n+1,A[i].fi+A[i].se-INF)-vc;
		c+=F[c]++,B[i]={a,c},C[i]={b,c};
	}
	sort(B+1,B+n+1);
	sort(C+1,C+n+1);
	for(int i=1;i<=q;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		a=INF-a,b=INF-b,c=INF-c;
		a=upper_bound(va+1,va+n+1,a)-va-1;
		b=upper_bound(vb+1,vb+n+1,b)-vb-1;
		c=upper_bound(vc+1,vc+n+1,c)-vc-1;
		Q[i]={a,b,c,i};
	}
	sort(Q+1,Q+q+1,comp);
	int l=0,r=0;
	for(int i=1;i<=q;i++)
	{
		while(l<Q[i].l) l++,update(B[l].se,++cc[B[l].se]==2);
		while(l>Q[i].l) update(B[l].se,--cc[B[l].se]==2),l--;
		while(r<Q[i].r) r++,update(C[r].se,++cc[C[r].se]==2);
		while(r>Q[i].r) update(C[r].se,--cc[C[r].se]==2),r--;
		ans[Q[i].pos]=get(Q[i].u);
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

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