oj.uz

Submission #491652

# Submission time Handle Problem Language Result Execution time Memory
491652 2021-12-03T17:19:13 Z doowey Distributing Candies (IOI21_candies) C++17
100 / 100
 2428 ms 38420 KB 
#include <bits/stdc++.h>
#include "candies.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)2e5 + 100;
const ll inf = (ll)1e18;

struct Node{
    ll mx;
    ll low;
    ll lzy;
};

Node T[N * 4 + 512];

void push(int node, int cl, int cr){
    T[node].mx += T[node].lzy;
    T[node].low += T[node].lzy;
    if(cl != cr){
        T[node * 2].lzy += T[node].lzy;
        T[node * 2 + 1].lzy += T[node].lzy;
    }
    T[node].lzy = 0;
}

void upd(int node, int cl, int cr, int tl, int tr, ll v){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        T[node].lzy += v;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd(node * 2, cl, mid, tl, tr, v);
    upd(node * 2 + 1, mid + 1, cr, tl, tr, v);
    T[node].mx = max(T[node * 2].mx, T[node * 2 + 1].mx);
    T[node].low = min(T[node * 2].low, T[node * 2 + 1].low);
}

vector<pii> Q[N];


ll getval(int node, int cl, int cr, int tl, int tr, int ff){
    push(node, cl, cr);
    if(cr < tl || cl > tr) {
        if(ff == 0) return inf;
        else return -inf;
    }
    if(cl >= tl && cr <= tr){
        if(ff == 0){
            return T[node].low;
        }
        else{
            return T[node].mx;
        }
    }
    int mid = (cl + cr) / 2;
    ll lef = getval(node * 2, cl, mid, tl, tr, ff);
    ll rig = getval(node * 2 + 1, mid + 1, cr, tl, tr, ff);
    if(ff == 0)
        return min(lef, rig);
    else
        return max(lef, rig);
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v){
    int n = c.size();
    int q = l.size();
    int m = q + 2;
    upd(1, 0, m - 1, 0, m - 1, +inf);
    upd(1, 0, m - 1, 1, m - 1, -inf);
    for(int i = 0 ;i < q; i ++ ){
        Q[l[i]].push_back(mp(i + 2, +v[i]));
        Q[r[i] + 1].push_back(mp(i + 2, -v[i]));
    }
    int iq;
    int nex;
    ll las;
    ll fir, bef;
    vector<int> soln;
    ll xx;
    for(int i = 0 ; i < n; i ++ ){
        for(auto x : Q[i]){
            upd(1, 0, m - 1, x.fi, m - 1, x.se);
        }
        iq = m - 1;
        for(int lg = 18; lg >= 0; lg -- ){
            nex = (iq - (1 << lg));
            if(nex < 0) continue;
            if(getval(1, 0, m - 1, nex, m - 1, 1) - getval(1, 0, m - 1, nex, m - 1, 0) <= c[i]){
                iq = nex;
            }
        }
        las = getval(1, 0, m - 1, m - 1, m - 1, 0);
        fir = getval(1, 0, m - 1, iq, iq, 0);
        bef = getval(1, 0, m - 1, iq - 1, iq - 1, 0);
        if(bef > fir){
            ll wall_low = getval(1, 0, m - 1, iq, m - 1, 0);
            xx = las - wall_low;
        }
        else{
            ll wall_high = getval(1, 0, m - 1, iq, m - 1, 1);
            xx = c[i] - (wall_high - las);
        }
        soln.push_back(xx);
    }
    return soln;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4876 KB Output is correct
3 Correct 4 ms 5140 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 13 ms 5280 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2313 ms 36760 KB Output is correct
2 Correct 2277 ms 35900 KB Output is correct
3 Correct 2195 ms 35700 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 257 ms 29480 KB Output is correct
3 Correct 791 ms 11064 KB Output is correct
4 Correct 1896 ms 37848 KB Output is correct
5 Correct 2428 ms 38204 KB Output is correct
6 Correct 2185 ms 38420 KB Output is correct
7 Correct 2223 ms 37956 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 139 ms 27916 KB Output is correct
4 Correct 717 ms 9176 KB Output is correct
5 Correct 1681 ms 32112 KB Output is correct
6 Correct 1968 ms 32632 KB Output is correct
7 Correct 1969 ms 33216 KB Output is correct
8 Correct 1645 ms 32124 KB Output is correct
9 Correct 1454 ms 33368 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4876 KB Output is correct
3 Correct 4 ms 5140 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 13 ms 5280 KB Output is correct
6 Correct 2313 ms 36760 KB Output is correct
7 Correct 2277 ms 35900 KB Output is correct
8 Correct 2195 ms 35700 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 257 ms 29480 KB Output is correct
11 Correct 791 ms 11064 KB Output is correct
12 Correct 1896 ms 37848 KB Output is correct
13 Correct 2428 ms 38204 KB Output is correct
14 Correct 2185 ms 38420 KB Output is correct
15 Correct 2223 ms 37956 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 139 ms 27916 KB Output is correct
19 Correct 717 ms 9176 KB Output is correct
20 Correct 1681 ms 32112 KB Output is correct
21 Correct 1968 ms 32632 KB Output is correct
22 Correct 1969 ms 33216 KB Output is correct
23 Correct 1645 ms 32124 KB Output is correct
24 Correct 1454 ms 33368 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 689 ms 9136 KB Output is correct
27 Correct 250 ms 28996 KB Output is correct
28 Correct 1787 ms 36396 KB Output is correct
29 Correct 2008 ms 36804 KB Output is correct
30 Correct 2196 ms 37072 KB Output is correct
31 Correct 2160 ms 37252 KB Output is correct
32 Correct 2180 ms 37240 KB Output is correct