Submission #43977

#	Time	Username	Problem	Language	Result	Execution time	Memory
43977		wzy	Candies (JOI18_candies)	C++11	0 / 100	5 ms	2040 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define piii pair<int, pii> 
#define F first
#define S second
long long sum  = 0 ;
set<int> s;
int n;
set<pii> v;
vector<int> x;
set<piii>::iterator gt[200005];
bool tp = false , ts = false;
pii tpx , tsx;
int prefixo[200005];
bool ct[200005];
set<piii> dsu;
bool debug = false;

void insere(pii t){
	sum += x[t.S];
	if(t.S) v.erase(pii(-x[t.S-1] , t.S-1));
	if(t.S + 1 < n) v.erase(pii(-x[t.S + 1] , t.S + 1));
	v.erase(t);
	bool ala = false;
	if(tp){
		if(t.S == tpx.F + 2) tpx.F = t.S, ala = true;
		if(t.S == tpx.S + 2) tpx.S = t.S, ala = true;
	}
	if(ts){
		if(t.S == tsx.F - 2) tsx.F = t.S, ala = true;
		if(t.S == tsx.S + 2) tsx.S = t.S, ala = true;
	}
	if(!ts && t.S == n - 1){
		ts = true;
		tsx.F = t.S, ala = true;
		tsx.S = t.S, ala = true;
	}
	if(!tp && t.S == 0){
		tp = true;
		tpx.F = t.S, ala = true;
		tpx.S = t.S, ala = true;
	}
	if(ala) return;
	if(t.S - 2 >= 0 && t.S + 2 < n && ct[t.S - 2] && ct[t.S + 2]){
		set<piii>::iterator itL = gt[t.S - 2] , itR = gt[t.S + 2];
		ct[t.S - 2]  = false, ct[t.S + 2] = false;
		piii nw;
		piii uL = *itL , uR = *itR;
		nw.F = uL.F ;
		nw.F += uR.F;
		nw.F += x[t.S];
		nw.S.F = uL.S.F;
		nw.S.S = uR.S.S;
		dsu.erase(itL) , dsu.erase(itR);
		ct[nw.S.F] = true, ct[nw.S.S] = true;
		dsu.insert(nw);
		gt[nw.S.F] = dsu.find(nw) , gt[nw.S.S] = dsu.find(nw);
	}
	else if(t.S - 2 >= 0 && ct[t.S - 2]){
		set<piii>::iterator it = gt[t.S - 2];
		ct[t.S - 2] = false;
		piii nw = *it;
		nw.F -= x[t.S + 1];
		nw.S.S = t.S ;
		nw.F += x[t.S];
		ct[t.S] = true;
		dsu.erase(gt[t.S - 2]);
		dsu.insert(nw);
		gt[t.S] = dsu.find(nw);
		gt[nw.S.F] = dsu.find(nw);
	}
	else if(t.S + 2 < n && ct[t.S + 2]){
		set<piii>::iterator it = gt[t.S + 2];
		ct[t.S +2 ] = false;
		piii nw = *it;
		nw.F -= x[t.S - 1];
		nw.S.F = t.S;
		nw.F += x[t.S];
		ct[t.S] = true;
		dsu.erase(gt[t.S + 2]);
		dsu.insert(nw);
		gt[nw.S.S] = dsu.find(nw);
		gt[nw.S.F] = dsu.find(nw);

	}
	else{
		piii nw;
		nw.F = -((t.S ? x[t.S - 1] : 0) + (((t.S + 1) < n) ? x[t.S + 1] : 0)) + x[t.S];
		nw.S.F = t.S , nw.S.S = t.S;
		ct[t.S] = true;
		dsu.insert(nw);
		gt[t.S] = dsu.find(nw);

	}
}


void flipa(){
	set<piii>::iterator it = dsu.begin();
	piii w = *it;
	ct[w.S.F] = false;
	ct[w.S.S] = false;
	sum = sum - w.F;
	piii nw;
	nw.F = -w.F;
	nw.S.F = w.S.F - 1 , nw.S.S = w.S.S + 1;
	bool ala = false;
	if(nw.S.F == 0){
		tp = true;
		tpx = nw.S;
		ala = true;
	}
	if(nw.S.S == n - 1){
		ts = true;
		tsx = nw.S;
		ala = true;
	}
	if(tp && nw.S.F -2 == tpx.S){
		tpx.S = nw.S.S;
		ala = true;
	}
	if(ts && nw.S.S + 2 == tsx.F){
		tsx.F = nw.S.S ;
		ala = true;
	}
	dsu.erase(it);
	if(nw.S.S + 1 < n){
		v.erase(pii(-x[nw.S.S + 1] , nw.S.S + 1));
	}
	if(nw.S.F - 1 >= 0){
		v.erase(pii(-x[nw.S.F - 1] , nw.S.F - 1));
	}
	if(ala) return;
	ct[nw.S.F] = 1 , ct[nw.S.S] = 1;
	if(nw.S.S + 1 < n){
		nw.F += -x[nw.S.S + 1];
	}
	if(nw.S.F - 1 >= 0){
		nw.F += -x[nw.S.F - 1];
	}
	dsu.insert(nw);
	gt[nw.S.F] = dsu.find(nw) , gt[nw.S.S] = dsu.find(nw);
}


int flip(){
	if(dsu.size() == 0) return 0;
	set<piii>::iterator it = dsu.begin();
	piii w = *it;
 	return sum - w.F;
}


int custo(int i , int j){
	int sumj = 0;
	for(int w = i ; w <= j ; w+= 2){
		sumj += x[w];
	}
	return sumj;
}



int32_t main(){
	cin>>n;
	for(int i = 0 ; i < n ; i++) prefixo[i] = 0;
	for(int i = 0 ; i < n; i ++){
		int xx;
		cin>>xx;
		v.insert(pii(-xx , i));
		x.push_back(xx);
		if(i > 0) prefixo[i] += prefixo[i-1] + xx;
		else prefixo[i] = xx;
	}
	for(int j = 1 ; j <= n/2  + (n%2 ? 1 : 0); j++){
		pii t;
		if(v.size())
		t = *v.begin();
		else(t.F = (int) 1e18);
		int jk = flip();
		if(tp){
			int jw = tpx.S + 2;
			while(jw < n && ct[jw]){
				ct[jw] = false;
				piii k = *gt[jw];
				dsu.erase(gt[jw]);
				tpx.S = k.S.S;
				jw= k.S.S + 2;
			}
		}
		if(ts){
			int jw = tsx.F  - 2;
			while(jw >= 0 && ct[jw]){
				ct[jw]  =false;
				piii k = *gt[jw];
				dsu.erase(gt[jw]);
				tsx.F = k.S.F;
				jw = k.S.F - 2;
			} 
		}
		if(sum -t.first >= jk ){
			insere(t);
		}
		else{
			flipa();
		}
		printf("%lld\n" , sum);
	}
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92