Submission #697600

#	Time	Username	Problem	Language	Result	Execution time	Memory
697600		keta_tsimakuridze	Candies (JOI18_candies)	C++14	100 / 100	495 ms	69612 KiB

candies

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
#define Pii pair<int,pii>
using namespace std;
const int N = 2e5 + 5, inf = 1e14; // !
int ans[N], a[N], p[N];
set<pii> S;
set<Pii> s;
struct node {
    pair<int, pii> best[2];
    pii R[2], L[2];
} t[4 * N], Z;

node merge(node a, node b) {

    node c;
    for(int t = 0; t < 2; t++) c.R[t] = max(a.R[t], b.R[t]), c.L[t] = min(a.L[t], b.L[t]);

    for(int t = 0; t < 2; t++)
    c.best[t] = max(a.best[t], b.best[t]),
    c.best[t] = max(c.best[t], {{b.R[t].f - a.L[t^1].f}, {a.L[t^1].s + 1, b.R[t].s}});
    return c;
}
void build(int u, int l, int r) {
    if(l == r) {
        t[u].best[0].f = t[u].best[1].f = -inf;
        t[u].R[l % 2] = {(l % 2 ? p[l] : -p[l]), l}; t[u].R[1 - l % 2].f = -inf;
        t[u].L[l % 2] = {(l % 2 ? -p[l] : p[l]), l}; t[u].L[1 - l % 2].f = inf;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
int n;
node get(int u, int st, int en, int l, int r) {
    if(l > en || r < st) return Z;
    if(st <= l && r <= en) return t[u];
    int mid = (l + r) / 2;

    return merge(get(2 * u, st ,en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
void add(int l, int r) {
    if(l > r) return;
    Pii p = get(1, l - 1, r, 0, n).best[l % 2];
    S.insert({l, r});
    s.insert(p);
}
main(){
    cin >> n;
    int cur = 0;
    vector<int> sum(2);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i % 2] += a[i];
        p[i] = p[i - 1] + (i % 2 ? -a[i] : a[i]);
    }

    for(int t = 0; t < 2; t++) Z.R[t].f = Z.best[t].f = -inf, Z.L[t].f = inf;
    build(1, 0, n);
    if(n % 2) cur = sum[1], add(1, n);
    else {
        if(sum[1] <= sum[0]) cur = sum[0];
        else cur = sum[1];
        vector<int> x(2);
        for(int i = 1; i <= n; i ++) {
            // i, i + 1 vigebt uechveli eseni gvawyobs
            if(i % 2 == 0) cur = max(cur, x[1] + sum[0] - x[0] - a[i]);
            x[i % 2] += a[i];
        }
        if(cur == sum[0]) add(2, n);
        else if(cur == sum[1]) add(1, n - 1);
        else {
            x[0] = x[1] = 0;
            for(int i = 1; i < n; i ++) {
                if(i % 2 == 0 && cur == x[1] + sum[0] - x[0] - a[i]) {
//                    cout << i << endl;
                    add(1, i - 1);
                    add(i + 2, n);
                    break;
                }
                x[i % 2] += a[i];
            }
        }
    }
    ans[(n + 1) /2 ] = cur;
    for(int i = (n + 1) / 2 - 1; i >= 1; i--) {
        Pii p = (*--s.end());
        int l = p.s.f, r = p.s.s;
        s.erase(p);
        cur += p.f; ans[i] = cur;
        pii cur = *--S.upper_bound({l + 1, 0});
        S.erase(cur);
        if(cur.f <= l - 2) add(cur.f, l - 2);

        if(cur.s >= r + 2) add(r + 2, cur.s);
        if(l < r) add(l + 1, r - 1);

    }
    for(int i = 1; i <= (n + 1) / 2; i++) cout << ans[i] << " ";
 }

Compilation message (stderr)

candies.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main(){
      | ^~~~

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