oj.uz

Submission #773190

# Submission time Handle Problem Language Result Execution time Memory
773190 2023-07-04T16:25:00 Z GrindMachine Candies (JOI18_candies) C++17
100 / 100
 481 ms 30348 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi of apio 2007 backup

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n; cin >> n;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];

    set<array<ll,3>> segs;
    set<array<ll,3>> costs;
    rep1(i,n){
        segs.insert({i,i+1,a[i]});
        costs.insert({a[i],i,i+1});
    }

    ll ans = 0;

    rep1(iter,ceil2(n,2)){
        auto [mx,l,r] = *costs.rbegin();
        ans += mx;
        cout << ans << endl;

        auto it = segs.lower_bound({l,r,mx});

        array<ll,3> ar1, ar2;
        ar1.fill(-1);
        ar2.fill(-1);

        if(it != segs.begin()){
            ar1 = *prev(it); 
        }
        if(next(it) != segs.end()){
            ar2 = *next(it);
        }

        if(ar1[0] != -1){
            segs.erase(ar1);
            costs.erase({ar1[2], ar1[0], ar1[1]});
        }

        if(ar2[0] != -1){
            segs.erase(ar2);
            costs.erase({ar2[2], ar2[0], ar2[1]});
        }

        if(ar1[0] != -1 and ar2[0] != -1){
            ll l = ar1[0], r = ar2[1], cost = ar1[2]+ar2[2]-mx;
            segs.insert({l,r,cost});
            costs.insert({cost,l,r});
        }

        segs.erase({l,r,mx});
        costs.erase({mx,l,r});
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 3 ms 608 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 608 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Correct 473 ms 30284 KB Output is correct
22 Correct 469 ms 30284 KB Output is correct
23 Correct 481 ms 30240 KB Output is correct
24 Correct 226 ms 30148 KB Output is correct
25 Correct 231 ms 30168 KB Output is correct
26 Correct 228 ms 30152 KB Output is correct
27 Correct 232 ms 30316 KB Output is correct
28 Correct 248 ms 30320 KB Output is correct
29 Correct 233 ms 30328 KB Output is correct
30 Correct 287 ms 30320 KB Output is correct
31 Correct 253 ms 30344 KB Output is correct
32 Correct 278 ms 30348 KB Output is correct
33 Correct 337 ms 30132 KB Output is correct
34 Correct 366 ms 30112 KB Output is correct
35 Correct 316 ms 30144 KB Output is correct
36 Correct 462 ms 30288 KB Output is correct
37 Correct 443 ms 30320 KB Output is correct
38 Correct 479 ms 30284 KB Output is correct
39 Correct 230 ms 30176 KB Output is correct
40 Correct 216 ms 30168 KB Output is correct
41 Correct 222 ms 30156 KB Output is correct
42 Correct 245 ms 30280 KB Output is correct
43 Correct 239 ms 30280 KB Output is correct
44 Correct 250 ms 30304 KB Output is correct
45 Correct 251 ms 30332 KB Output is correct
46 Correct 248 ms 30248 KB Output is correct
47 Correct 264 ms 30320 KB Output is correct
48 Correct 314 ms 30040 KB Output is correct
49 Correct 339 ms 30152 KB Output is correct
50 Correct 323 ms 30124 KB Output is correct