oj.uz

Submission #160161

# Submission time Handle Problem Language Result Execution time Memory
160161 2019-10-26T07:52:38 Z combi1k1 Candies (JOI18_candies) C++14
0 / 100
 5 ms 632 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll      long long
#define X       first
#define Y       second

#define FOR(i,a,b)  for(int i = a ; i <= b ; ++i)

const int   N   = 2e5 + 1;

typedef pair<int,int>   ii;

set<ii>  S1;
set<int> S2;

int a[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    ll  ans = 0;

    FOR(i,1,n)  {
        cin >> a[i];
        S1.insert({a[i],i});
        S2.insert(i);
    }
    S2.insert(0);
    S2.insert(N);
    FOR(i,1,(n + 1) / 2)    {
        int j = (*--S1.end()).Y;

        cout << (ans += a[j]) << "\n";

        S1.erase(ii(a[j],j));
        S2.erase(j);

        a[j] = -a[j];

        auto L = S2.upper_bound(j);
        auto R = L--;

        int cnt = 0;

        if (*L >= 1)    {
            a[j] += a[*L];
            S1.erase(ii(a[*L],*L));
            S2.erase(*L);
            cnt++;
        }
        if (*R <= n)    {
            a[j] += a[*R];
            S1.erase(ii(a[*R],*R));
            S2.erase(*R);
            cnt++;
        }

        if (cnt == 2)
            S1.insert(ii(a[j],j)),
            S2.insert(j);
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -