Submission #960895

#	Time	Username	Problem	Language	Result	Execution time	Memory
960895		pcc	Synchronization (JOI13_synchronization)	C++17	0 / 100	310 ms	17388 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;
set<int> ls,rs;
int N,M,Q;
int op[mxn*2];
bitset<mxn> done;

struct SEG{
#define mid ((l+r)>>1)
	pii seg[mxn*4];
	SEG(){
		for(auto &i:seg)i.fs = i.sc = -1e9;
	}
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now].sc = max(seg[now].sc,v);
			return;
		}
		if(mid>=e)modify(now*2+1,l,mid,s,e,v);
		if(mid<s)modify(now*2+2,mid+1,r,s,e,v);
		seg[now].fs = max({seg[now*2+1].fs,seg[now*2+1].sc,seg[now*2+2].fs,seg[now*2+2].sc});
		return;
	}
	int getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return max(seg[now].fs,seg[now].sc);
		if(mid>=e)return max(seg[now].sc,getval(now*2+1,l,mid,s,e));
		else if(mid<s)return max(seg[now].sc,getval(now*2+2,mid+1,r,s,e));
		else return max({seg[now].sc,getval(now*2+1,l,mid,s,e),getval(now*2+2,mid+1,r,s,e)});
	}
#undef mid
};

SEG lseg,rseg;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>Q;
	for(int i = 1;i<N;i++){
		int a;
		cin>>a>>a;
	}
	for(int i = 1;i<=M;i++)cin>>op[i];
	for(int i = 1;i<=N;i++){
		ls.insert(i);
		rs.insert(i);
		lseg.modify(0,1,N,i,i,-i);
		rseg.modify(0,1,N,i,i,i);
	}
	rs.insert(0);
	ls.insert(N+1);
	ls.erase(N);
	rs.erase(1);
	for(int i = 1;i<=M;i++){
		int id = op[i];
		if(done[id]){
			done[id] = false;
			ls.insert(id);
			rs.insert(id+1);
			continue;
		}
		done[id] = true;
		ls.erase(id);
		rs.erase(id+1);
		auto lp = *(--rs.lower_bound(id));
		auto rp = *(ls.lower_bound(id+1));
		lseg.modify(0,1,N,lp,rp,lseg.getval(0,1,N,lp,rp));
		rseg.modify(0,1,N,lp,rp,rseg.getval(0,1,N,lp,rp));
	}
	while(Q--){
		int k;
		cin>>k;
		cout<<rseg.getval(0,1,N,k,k)+lseg.getval(0,1,N,k,k)+1<<'\n';
	}
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40