oj.uz

답안 #204874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
204874 2020-02-27T11:50:57 Z egekabas Candies (JOI18_candies) C++14
0 / 100
 6 ms 632 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pii;
typedef pair<ld, ld>  pld;
ll prt[200009];
ll val[200009];
ll lef[200009];
ll rig[200009];
ll evsum[200009];
ll oddsum[200009];

ll findprt(ll x){
    if(prt[x] == x)
        return x;
    return (prt[x] = findprt(prt[x]));
}
void merge(ll x, ll y){
    x = findprt(x);
    y = findprt(y);
    if(x == y) return; 
    prt[x] = y;
    val[y] += val[x];
    lef[y] = min(lef[x], lef[y]);
    rig[y] = max(rig[x], rig[y]);
    evsum[y] += evsum[x];
    oddsum[y] += oddsum[x];
    
}
ll n;
ll a[200009];
ll ans[200009];
set<pll, greater<pll>> s;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n;
    for(ll i = 0; i < n; ++i){
        cin >> a[i];
        prt[i] = i;
        val[i] = a[i];
        lef[i] = rig[i] = i;
        if(i%2)
            oddsum[i] = a[i];
        else
            evsum[i] = a[i];
        s.insert({val[i], i});
    }
    ll sz = 1;
    ll cur = 0;
    while(sz <= (n+1)/2){
        pll curit = *s.begin();
        s.erase(s.begin());
        ll curnode = curit.ss;
        if((lef[curnode] == 0 || rig[curnode] == n-1) && (rig[curnode]-lef[curnode])%2 ){
            if(curit.ff < 0)
                continue;
        }
        else{
            ans[sz] = cur;
            ++sz;
        }
        cur += curit.ff;
        //cout << lef[curnode] << ' ' << rig[curnode] << '\n';
        ll befl = lef[curnode];
        if(lef[curnode]-1 >= 0){
            ll x = findprt(lef[curnode]-1);
            s.erase({val[x], x});
            merge(x, curnode);
        }
        curnode = findprt(curnode);
        if(rig[curnode]+1 < n){
            ll x = findprt(rig[curnode]+1);
            s.erase({val[x], x});
            merge(x, curnode);
        }
        curnode = findprt(curnode);
        if(befl%2 == 0)
            val[curnode] = oddsum[curnode]-evsum[curnode];
        else
            val[curnode] = evsum[curnode]-oddsum[curnode];
        s.insert({val[curnode], curnode});
    }
    for(ll i = 1; i <= (n+1)/2; ++i)
        cout << ans[i] << '\n';
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -