제출 #960900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960900		pcc	동기화 (JOI13_synchronization)	C++17	30 / 100	337 ms	19944 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>=s)modify(now*2+1,l,mid,s,e,v);
		if(mid<e)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);
	}
	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.upper_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: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40