oj.uz

Submission #715656

# Submission time Handle Problem Language Result Execution time Memory
715656 2023-03-27T12:27:09 Z fatemetmhr Candies (JOI18_candies) C++17
100 / 100
 387 ms 22624 KB 
// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

set <pair<ll, int>> seg, av;
ll a[maxn5], sum[maxn5], have[maxn5];
int pre[maxn5], l[maxn5], r[maxn5], nxt[maxn5];

inline int merge(int v){
    int u = nxt[v];
    int z = nxt[u];
    nxt[v] = z;
    if(z != -1)
        pre[z] = v;
    av.erase({-(sum[u] - 2 * have[u]), u});
    av.erase({-(sum[v] - 2 * have[v]), v});
    sum[v] += sum[u];
    have[v] += have[u];
    l[v] = min(l[v], l[u]);
    r[v] = max(r[v], r[u]);
    return v;
}

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

    int n; cin >> n;
    for(int i = 0; i < n; i++){
        cin >> sum[i];
        av.insert({-sum[i], i});
        l[i] = r[i] = i;
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[n - 1] = -1;
    ll cur = 0;
    for(int i = 1; i <= (n + 1) / 2; i++){
        int v = av.begin()->se;
        av.erase(av.begin());
        cur += sum[v] - 2 * have[v];
        have[v] = sum[v] - have[v];
        if(nxt[v] != -1)
            v = merge(v);
        if(pre[v] != -1)
            v = merge(pre[v]);
        if((r[v] - l[v] + 1) & 1)
            av.insert({-(sum[v] - 2 * have[v]), v});
        cout << cur << '\n';
    }
}

/*
5
3 5 1 7 6
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 580 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 580 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 349 ms 22492 KB Output is correct
22 Correct 387 ms 22552 KB Output is correct
23 Correct 381 ms 22536 KB Output is correct
24 Correct 162 ms 22456 KB Output is correct
25 Correct 148 ms 22300 KB Output is correct
26 Correct 143 ms 22348 KB Output is correct
27 Correct 149 ms 22604 KB Output is correct
28 Correct 148 ms 22560 KB Output is correct
29 Correct 149 ms 22500 KB Output is correct
30 Correct 161 ms 22544 KB Output is correct
31 Correct 156 ms 22496 KB Output is correct
32 Correct 157 ms 22472 KB Output is correct
33 Correct 238 ms 22348 KB Output is correct
34 Correct 252 ms 22360 KB Output is correct
35 Correct 251 ms 22292 KB Output is correct
36 Correct 358 ms 22604 KB Output is correct
37 Correct 346 ms 22624 KB Output is correct
38 Correct 358 ms 22516 KB Output is correct
39 Correct 150 ms 22388 KB Output is correct
40 Correct 140 ms 22296 KB Output is correct
41 Correct 142 ms 22384 KB Output is correct
42 Correct 150 ms 22496 KB Output is correct
43 Correct 149 ms 22604 KB Output is correct
44 Correct 150 ms 22488 KB Output is correct
45 Correct 163 ms 22512 KB Output is correct
46 Correct 160 ms 22536 KB Output is correct
47 Correct 155 ms 22496 KB Output is correct
48 Correct 233 ms 22312 KB Output is correct
49 Correct 239 ms 22344 KB Output is correct
50 Correct 247 ms 22248 KB Output is correct