oj.uz

Submission #457747

# Submission time Handle Problem Language Result Execution time Memory
457747 2021-08-07T11:10:49 Z Peti Distributing Candies (IOI21_candies) C++17
0 / 100
 3908 ms 71156 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(ert < temp.second)
            ki[x-maxn] = (long long)vc[x-maxn] + ertek(maxn-1) - temp.second;
        else
            ki[x-maxn] = ertek(maxn-1) - temp.second;
    } 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12748 KB Output is correct
2 Incorrect 10 ms 12684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12748 KB Output is correct
2 Incorrect 10 ms 12684 KB Output isn't correct
3 Halted 0 ms 0 KB -