Submission #1224827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224827		boclobanchat	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	472 ms	7500 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
struct query { int l,r,pos; };
const int MAXN=2e5+5;
const int sqr=500;
int cnt[MAXN],block[MAXN],block2[MAXN],A[MAXN],B[MAXN],val[MAXN],pos[MAXN],V[MAXN];
query Q[MAXN];
bool comp(query a,query b)
{
	if(a.l/sqr==b.l/sqr) return a.r<b.r;
	return a.l/sqr<b.l/sqr;
}
bool cnum(int a,int b) { return val[a]<val[b]; }
void update(int i,int val)
{
	block[i/sqr]-=(cnt[i]==1);
	block2[i/sqr]-=(cnt[i]==0);
	cnt[i]+=val;
	block[i/sqr]+=(cnt[i]==1);
	block2[i/sqr]+=(cnt[i]==0);
}
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]>>B[i];
	for(int i=1;i<=q;i++) 
	{
		cin>>val[i];
		V[i]=val[i],pos[i]=i;
	}
	sort(pos+1,pos+q+1,cnum);
	sort(V+1,V+q+1);
	for(int i=1;i<=n;i++)
	{
		int l=lower_bound(V+1,V+q+1,min(A[i],B[i]))-V-1;
		int r=lower_bound(V+1,V+q+1,max(A[i],B[i]))-V-1;
		Q[i]={l,r,i};
	}
	sort(Q+1,Q+n+1,comp);
	int l=0,r=0,cb=q/sqr;
	long long ans=0;
	for(int i=1;i<=q;i++) block2[i/sqr]++;
	for(int i=1;i<=n;i++)
	{
		while(l<Q[i].l) update(pos[++l],1);
		while(r<Q[i].r) update(pos[++r],1);
		while(l>Q[i].l) update(pos[l--],-1);
		while(r>Q[i].r) update(pos[r--],-1);
		int p=1,f=0;
		for(int j=cb;j+1;j--) if(block[j])
		{
			for(int k=(j+1)*sqr-1;;k--) if(cnt[k]==1)
			{
				p=k+1;
				break;
			}
			break;
		}
		if(p!=1&&A[Q[i].pos]<B[Q[i].pos]) f=1;
		while(p<=q&&p%sqr) f^=(cnt[p++]==0);
		if(p<=q)
		{
			p/=sqr;
			while(p<=cb) f^=(block2[p++]&1);
		}
		if(f) ans+=B[Q[i].pos];
		else ans+=A[Q[i].pos];
	}
	cout<<ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65