Submission #68727539

---

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
using namespace std;

using ll=long long;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using P=pair<int,int>;
using vi=vc<int>;
const uint mod=998244353;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint& operator+=(const mint&r){return s(v+r.v);}
	mint&operator-=(const mint&r){return s(v+mod-r.v);}
	mint&operator*=(const mint&r){v=(unsigned long long)v*r.v%mod;return *this;}
	mint&operator/=(const mint&r){return *this*=r.inv();}
	mint operator+(const mint&r)const{return mint(*this)+=r;}
	mint operator-(const mint&r)const{return mint(*this)-=r;}
	mint operator*(const mint&r)const{return mint(*this)*=r;}
	mint operator/(const mint&r)const{return mint(*this)/=r;}
	mint pow(ll n)const{
		if(n<0)return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
};
#define INF 100000000000000000LL

void solve(){
	int n,q;
	cin>>n>>q;
	vc<P> at(n);
	vc<int> B(n);
	for(int i=0;i<n;i++) cin>>at[i].b>>at[i].a;
	for(int i=0;i<n;i++) cin>>B[i];
	sort(at.begin(),at.end());
	sort(B.begin(),B.end(), greater <int>());
	int S = min(n, 4000);
	int m=n-S;
	vc<int> A(m);
	for(int i=0;i<m;i++) A[i] = at[i+S].b;
	sort(A.begin(),A.end(),greater <int>());

	vc<ll> sa(m+1), sb(n+1);
	auto consta=[&]()->void{
		sa[0]=0;
		for(int i=0;i<m;i++) sa[i+1]=sa[i]+A[i];
	};
	auto constb=[&]()->void{
		sb[0]=0;
		for(int i=0;i<n;i++) sb[i+1]=sb[i]+B[i];
	};

	consta();
	constb();
	vc<int> opt(S+1);
	vc<ll> ans(S+1);
	auto find_opt=[&](int d,int l,int r){
		ll mx=-INF;
		for(int i=l;i<=r;i++){
			if(i+d<=n&&mx<sa[i]-sb[i+d]){
				mx=sa[i]-sb[i+d];
				opt[d]=i;
			}
		}
		ans[d]=mx;
	};
	auto recur_opt=[&](int a,int b,int l,int r, auto self){
		if(a>=b) return;
		if(a+1==b) find_opt(a,l,r);
		else{
			int m=(a+b)/2;
			find_opt(m,l,r);
			self(a,m,l,opt[m],self);
			self(m+1,b,opt[m],r,self);
		}
	};
	auto pre_calc=[&]()->void{
		recur_opt(0,S+1,0,m,recur_opt);
	};
	pre_calc();
	//for(int i=0;i<=S;i++) cout<<i<<" "<<ans[i]<<endl;
	vc<P> zan(S);
	for(int i=0;i<S;i++) zan[i]=P(at[i].b,at[i].a);
	sort(zan.begin(),zan.end(),greater<P>());
	int th=at[S-1].a;
	priority_queue <int, vector <int>, greater <int> > que;
	for(int i=0;i<S;i++) que.push(at[i].a);
	for(int i=0;i<=q;i++){
		//find answer in res
		ll res=ans[0],sum=0;
		for(int j=0;j<S;j++){
			sum+=zan[j].a;
			res=max(res,sum+ans[j+1]);
		}
		cout<<res<<endl;
		if(i==q) break;
		int x,y;
		cin>>x>>y;
		//x=rand()%(1<<30), y=rand()%(1<<30);

		ll a=res%(1LL<<30);
		x^=a, y^=a;

		//y = i+n+1;

		que.push(y);
		int mn=que.top();que.pop();
		if(mn<y){
			for(int j=0;j<S;j++){
				if(zan[j].b==mn){
					zan[j]=P(x,y);
					for(int k=j;k<S-1;k++){
						if(zan[k+1].a>x) swap(zan[k],zan[k+1]);
						else break;
					}
					for(int k=j;k>0;k--){
						if(zan[k-1].a<x) swap(zan[k],zan[k-1]);
						else break;
					}
					break;
				}
			}
			if(mn==th){
				//cout<<"YES"<<endl;
				//reconstruct whole thing
				for(int j=0;j<S;j++) at[j]=P(zan[j].b,zan[j].a);
				sort(at.begin(),at.end());
				for(int i=0;i<m;i++) A[i] = at[i+S].b;
				sort(A.begin(),A.end(),greater <int>());
				consta();
				pre_calc();
				for(int i=0;i<S;i++) zan[i]=P(at[i].b,at[i].a);
				sort(zan.begin(),zan.end(),greater<P>());
				th=at[S-1].a;
				while(!que.empty()) que.pop();
				for(int i=0;i<S;i++) que.push(at[i].a);
			}
		}
	}
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int T=1;
	while(T--) solve();
}

Submission Info

Compile Error

./Main.cpp:2:13: warning: unknown pragma ignored [-Wunknown-pragmas]
#pragma GCC optimize ("Ofast")
            ^
./Main.cpp:3:13: warning: unknown pragma ignored [-Wunknown-pragmas]
#pragma GCC optimize ("unroll-loops")
            ^
2 warnings generated.

Judge Result