Submission #70397

#	Time	Username	Problem	Language	Result	Execution time	Memory
70397		elitewantsyou	Candies (JOI18_candies)	C++14	100 / 100	876 ms	25860 KiB

candies

#include <bits/stdc++.h>

#define fi first
#define se second
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );

const long long N = 200200;
const long long Q = 200200;
const long long mod = 998244353;
const long long MAGIC = sqrt(N);

using namespace std;

int n;
long long a[N];
set < int > s;
set < pair < long long, int > > f;

void solve()
{
        cin >> n;
        for(int i = 1; i <= n; i++){
                cin >> a[i];
                s.insert(i);
                f.insert({a[i], i});
        }
        long long ans = 0;
        a[0] = a[n + 1] = -1e15;
        s.insert(0);
        s.insert(n + 1);
        for(int i = 1; i <= (n + 1) / 2; i++){
                int x = (--f.end())->se;
                f.erase(--f.end());
                s.erase(x);
                ans += a[x];
                a[x] = - a[x];
                auto p = s.lower_bound(x);
                if(p != s.end()){
                        a[x] += a[*p];
                        f.erase({a[*p], *p});
                        s.erase(p);
                }
                p = s.lower_bound(x);
                if(p != s.begin()){
                        p--;
                        a[x] += a[*p];
                        f.erase({a[*p], *p});
                        s.erase(p);
                }
                s.insert(x);
                f.insert({a[x], x});
                cout << ans << "\n";
        }
}

bool mtest = false; int main()
{
        //fin("input.txt");
        //fout("output.txt");
        //fin("island.in");
        //fout("island.out");
        ios_base::sync_with_stdio(0);
        int TE = 1;
        if(mtest)
                cin >> TE;
        while(TE--)
                solve();
        return 0;
}

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