Submission #933024

#	Time	Username	Problem	Language	Result	Execution time	Memory
933024		FzArK	Candies (JOI18_candies)	C++17	0 / 100	2 ms	604 KiB

candies

#include<bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define clr(x) vector<int>().swap(x);
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vector<int>>
#define vii vector<pii>
#define random mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnd(time(0));
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define le v * 2
#define re v * 2 + 1
#define tm (tl + tr) / 2
#define no {cout << "NO" << endl; return;}
#define yes {cout << "YES" << endl; return;}
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
const ll INF=9e18;
const ll MN=-2e9;
const ll MX=2e5+9;
const ll MXX=2e9;
const ll SQ=6e2;
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll PP=1e6+3;
const ll P2=1299827;
const ld PI=3.141592653589793;
const ld eps=1e-11;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
typedef tree<ll, null_type, greater_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
    ordered_set;

int n, a[MX];
ll ans[MX];
pll save[MX];
set<array<ll,4>> Q;
set<pll> S;

void solve() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    for (int i=1; i<=n; i++) {
        Q.insert({a[i], 0, i, i});
        S.insert({i, i});
        save[i] = {a[i], 0};
    }
    int k = 1;
    ll res = 0;
    while (k <= (n + 1) / 2) {
        array<ll,4> x = *(--Q.end()); Q.erase(--Q.end());
        ll tot = x[0], sub = x[1], add = tot + sub, l = x[2], r = x[3], L = l, R = r;
        {// get
            res += tot, ckmax(ans[k], res), k += 1;
            if (l == 1 && r == n) break;
        }
        {// self
            auto it = S.lower_bound(make_pair(L, R));
            assert (*it == make_pair(L, R)); S.erase(it);
        }
        {// left
            auto it = S.lower_bound(make_pair(L, R));
            if (it != S.begin()) {
                it--;
                ll lf = it -> F, rt = it -> S; S.erase(it);
                ll tt = save[lf].F, sb = save[lf].S, ad = tt + sb;
                Q.erase(Q.find({tt, sb, lf, rt}));
                l = lf, add += sb, sub += ad;
            }
        }
        {// right
            auto it = S.upper_bound(make_pair(L, R));
            if (it != S.end()) {
                ll lf = it -> F, rt = it -> S; S.erase(it);
                ll tt = save[lf].F, sb = save[lf].S, ad = tt + sb;
                Q.erase(Q.find({tt, sb, lf, rt}));
                r = rt, add += sb, sub += ad;
            }
        }
        {// push
            tot = sub - add, sub = add;
            S.insert({l, r});
            save[l] = {tot, sub};
            Q.insert({tot, sub, l, r});
        }
    }
    for (int i=1; i<k; i++) {
        cout << ans[i] << endl;
    }
}

int main() {
    FAST;
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

/*

4
100 1 1 100

7
50 100 30 1 30 100 50

*/

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