#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);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
2040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
2040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
