Submission #457747

#	Time	Username	Problem	Language	Result	Execution time	Memory
457747		Peti	Distributing Candies (IOI21_candies)	C++17	0 / 100	3908 ms	71156 KiB

candies

#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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33