oj.uz

Submission #457823

# Submission time Handle Problem Language Result Execution time Memory
457823 2021-08-07T12:11:15 Z Peti Distributing Candies (IOI21_candies) C++17
100 / 100
 4166 ms 73012 KB 
#include <bits/stdc++.h>
#include "candies.h"

using namespace std;

const int maxn = 1<<18;
const long long INF = (long long)1e17;

vector<pair<int, int>> st[maxn<<1];
pair<long long, long long> st2[maxn<<1];
long long stadd[maxn<<1] = {};
vector<int> vc, ki;
int n;

void add_intervall(int L, int R, pair<int, int> d, int x = 1, int l = 0, int r = maxn){
    if(r <= L || R <= l)
        return;
    if(L <= l && r <= R){
        st[x].push_back(d);
        return;
    }
    int m = (l+r)>>1;
    add_intervall(L, R, d, x<<1, l, m);
    add_intervall(L, R, d, x<<1|1, m, r);
}

pair<long long, long long> get(long long c, pair<long long, long long> a, pair<long long, long long> b){
    return make_pair(min(a.first, b.first) + c, max(a.second, b.second) + c);
}

void upd(int x){
    if(x < maxn)
        st2[x] = get(stadd[x], st2[x<<1], st2[x<<1|1]);
    else
        st2[x].first = st2[x].second = stadd[x];
}

/*void prop(int x){
    if(x < maxn){
        stadd[x<<1] += stadd[x];
        stadd[x<<1|1] += stadd[x];
        stadd[x] = 0;
        upd(x<<1);
        upd(x<<1|1);
        upd(x);
    }
}*/

void add(int L, int R, long long c, int x = 1, int l = 0, int r = maxn){
    if(r <= L || R <= l)
        return;
    if(L <= l && r <= R){
        stadd[x] += c;
        upd(x);
        return;
    }
    int m = (l+r)>>1;
    add(L, R, c, x<<1, l, m);
    add(L, R, c, x<<1|1, m, r);
    upd(x);
}

long long ertek(int x){
    long long ret = 0;
    for(x += maxn; x > 0; x >>= 1)
        ret += stadd[x];
    return ret;
}

pair<long long, long long> get_minmax(int L, int R, int x = 1, int l = 0, int r = maxn){
    if(r <= L || R <= l)
        return make_pair(INF, -INF);
    if(L <= l && r <= R)
        return st2[x];
    int m = (l+r)>>1;
    return get(stadd[x], get_minmax(L, R, x<<1, l, m), get_minmax(L, R, x<<1|1, m, r));
}

void bejar(int x){;
    for(auto &d : st[x])
        add(d.first, maxn, d.second);
    if(x >= maxn && x-maxn < n){

        /*cout<<"sor: ";
        for(int i = 0; i <= n; i++)
            cout<<ertek(i)<<' ';
        cout<<'\n';*/

        int l = -1, r = maxn;
        while(l+1 < r){
            int m = (l+r)>>1;
            pair<long long, long long> temp = get_minmax(m, maxn);
            if(temp.second-temp.first <= (long long)vc[x-maxn])
                r = m;
            else
                l = m;
        }
        pair<long long, long long> temp = get_minmax(r, maxn);
        long long ert = (l == -1 ? 0 : ertek(l));
        if(l == -1 && max(temp.second - ert, ert - temp.first) <= (long long)vc[x-maxn]){
            ki[x-maxn] = ertek(maxn-1) - min(temp.first, 0ll);
        } else{
            if(ert < temp.second)
                ki[x-maxn] = (long long)vc[x-maxn] + ertek(maxn-1) - temp.second;
            else
                ki[x-maxn] = ertek(maxn-1) - temp.first;
        }
    } else if(x < maxn){
        bejar(x<<1);
        bejar(x<<1|1);
    }
    for(auto &d : st[x])
        add(d.first, maxn, -d.second);
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
    n = c.size();
    vc = c;
    ki.resize(n);

    for(int i = 0; i < (int)v.size(); i++)
        add_intervall(l[i], r[i]+1, make_pair(i, v[i]));
    bejar(1);

    return ki;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12720 KB Output is correct
2 Correct 11 ms 12720 KB Output is correct
3 Correct 18 ms 12932 KB Output is correct
4 Correct 18 ms 13008 KB Output is correct
5 Correct 35 ms 13148 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4077 ms 66288 KB Output is correct
2 Correct 4113 ms 70200 KB Output is correct
3 Correct 3832 ms 70144 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12700 KB Output is correct
2 Correct 1474 ms 48712 KB Output is correct
3 Correct 1076 ms 20700 KB Output is correct
4 Correct 3796 ms 72244 KB Output is correct
5 Correct 3828 ms 72480 KB Output is correct
6 Correct 3827 ms 73012 KB Output is correct
7 Correct 3846 ms 72380 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12620 KB Output is correct
2 Correct 15 ms 12744 KB Output is correct
3 Correct 807 ms 39116 KB Output is correct
4 Correct 1067 ms 18192 KB Output is correct
5 Correct 1948 ms 43600 KB Output is correct
6 Correct 1826 ms 44268 KB Output is correct
7 Correct 1899 ms 44848 KB Output is correct
8 Correct 1911 ms 43492 KB Output is correct
9 Correct 1977 ms 44976 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12720 KB Output is correct
2 Correct 11 ms 12720 KB Output is correct
3 Correct 18 ms 12932 KB Output is correct
4 Correct 18 ms 13008 KB Output is correct
5 Correct 35 ms 13148 KB Output is correct
6 Correct 4077 ms 66288 KB Output is correct
7 Correct 4113 ms 70200 KB Output is correct
8 Correct 3832 ms 70144 KB Output is correct
9 Correct 16 ms 12700 KB Output is correct
10 Correct 1474 ms 48712 KB Output is correct
11 Correct 1076 ms 20700 KB Output is correct
12 Correct 3796 ms 72244 KB Output is correct
13 Correct 3828 ms 72480 KB Output is correct
14 Correct 3827 ms 73012 KB Output is correct
15 Correct 3846 ms 72380 KB Output is correct
16 Correct 12 ms 12620 KB Output is correct
17 Correct 15 ms 12744 KB Output is correct
18 Correct 807 ms 39116 KB Output is correct
19 Correct 1067 ms 18192 KB Output is correct
20 Correct 1948 ms 43600 KB Output is correct
21 Correct 1826 ms 44268 KB Output is correct
22 Correct 1899 ms 44848 KB Output is correct
23 Correct 1911 ms 43492 KB Output is correct
24 Correct 1977 ms 44976 KB Output is correct
25 Correct 10 ms 12608 KB Output is correct
26 Correct 1115 ms 18580 KB Output is correct
27 Correct 1617 ms 48464 KB Output is correct
28 Correct 3895 ms 70712 KB Output is correct
29 Correct 3995 ms 71224 KB Output is correct
30 Correct 3816 ms 71280 KB Output is correct
31 Correct 4126 ms 71488 KB Output is correct
32 Correct 4166 ms 71692 KB Output is correct