Submission #1126267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126267		Tyx2019	Distributing Candies (IOI21_candies)	C++20	3 / 100	2768 ms	2162688 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define int long long 
#define debug(x) if(0) cout << #x << " is " << x << endl;
using namespace std; 
vector<int> C, L, R, V;
const int INF = 1e18;
int N, Q;
struct mxsubarr{
    int maxsum, sum, maxpref, maxsuf;
	int32_t endidx, prefendidx;
    mxsubarr(int a, int b, int c, int d, int e, int f){
        maxsum = a;
        sum = b;
        maxpref = c;
        maxsuf = d;
        endidx = e;
        prefendidx = f;
    }
};
mxsubarr* merge(mxsubarr* l, mxsubarr* r){
    int sum, maxpref, maxsuf, maxsum;
	int32_t endidx, prefendidx;
    sum = l->sum + r->sum;
    maxpref = max(l->maxpref, l->sum + r->maxpref);
    if(l->maxpref == maxpref) prefendidx = l->prefendidx;
    else prefendidx = r->prefendidx;
    maxsuf = max(r->maxsuf, r->sum + l->maxsuf);
    maxsum = max({l->maxsum, r->maxsum, l->maxsuf + r->maxpref});
    if(l->maxsum == maxsum) endidx = l->endidx;
    else if(r->maxsum == maxsum) endidx = r->endidx;
    else endidx = r->prefendidx;

    mxsubarr* ret = new mxsubarr(maxsum, sum, maxpref, maxsuf, endidx, prefendidx);
    return ret;
}
struct kadane{
    int S, E, M;
    int maxsum, sum, maxpref, maxsuf;
	int32_t endidx, prefendidx;
    kadane *l, *r;
    kadane(int _S, int _E){
        S = _S;
        E = _E;
        M = (S + E) >> 1;
        l = r = NULL;
        maxsum = sum = maxpref = maxsuf = 0;
        endidx = prefendidx = S;
    }
    void upd(int idx, int val){
		if(!l) l = new kadane(S, M);
		if(!r) r = new kadane(M + 1, E);
        if(S == E){
            maxsum = sum = maxpref = maxsuf = val;
            endidx = prefendidx = S;
            return;
        }
        if(idx <= M) l->upd(idx, val);
        else r->upd(idx, val);
        sum = l->sum + r->sum;
        maxpref = max(l->maxpref, l->sum + r->maxpref);
        if(l->maxpref == maxpref) prefendidx = l->prefendidx;
        else prefendidx = r->prefendidx;
        maxsuf = max(r->maxsuf, r->sum + l->maxsuf);
        maxsum = max({l->maxsum, r->maxsum, l->maxsuf + r->maxpref});
        if(l->maxsum == maxsum) endidx = l->endidx;
        else if(r->maxsum == maxsum) endidx = r->endidx;
        else endidx = r->prefendidx;
    }
    mxsubarr* query(int start, int end){
		if(!l) l = new kadane(S, M);
		if(!r) r = new kadane(M + 1, E);
        if(start == S && end == E) return new mxsubarr({maxsum, sum, maxpref, maxsuf, endidx, prefendidx});
        else if(end <= M){
            return l->query(start, end);
        }
        else if(start > M){
            return r->query(start, end);
        }
        else{
            return merge(l->query(start, M), r->query(M + 1, end));
        }
    }
}*seggs1, *seggs2;
struct node{
    //range add, range max, range min
    int S, E, M, mn, mx, ladd;
    node *l, *r;
    node(int _S, int _E){
        S = _S;
        E = _E;
        M = (S + E) >> 1;
        mn = mx = ladd = 0;
        if(S == E) return;
        l = new node(S, M);
        r = new node(M + 1, E);
    }
    void prop(){
        if(S == E) return;
        if(ladd != 0){
            l->mn += ladd;
            l->mx += ladd;
            r->mn += ladd;
            r->mx += ladd;
            l->ladd += ladd;
            r->ladd += ladd;
            ladd = 0;
        }
    }
    void upd(int start, int end, int val){
        prop();
        debug(S)
        debug(E)
        debug(start)
        debug(end)
        debug(val)
        if(start == S && end == E){
            ladd += val;
            mn += val;
            mx += val;
            return;
        }
        if(end <= M) l->upd(start, end, val);
        else if(start > M) r->upd(start, end, val);
        else{
            l->upd(start, M, val);
            r->upd(M + 1, end, val);
        }
        mn = min(l->mn, r->mn);
        mx = max(l->mx, r->mx);
    }
    int range_min(int start, int end){
        prop();
        if(start == S && end == E) return mn;
        if(end <= M) return l->range_min(start, end);
        else if(start > M) return r->range_min(start, end);
        else return min(l->range_min(start, M), r->range_min(M + 1, end));
    }
    int range_max(int start, int end){
        prop();
        if(start == S && end == E) return mx;
        if(end <= M) return l->range_max(start, end);
        else if(start > M) return r->range_max(start, end);
        else return max(l->range_max(start, M), r->range_max(M + 1, end));
    }
}*seggs3;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
    for(auto i:c) C.push_back(i);
    for(auto i:l) L.push_back(i);
    for(auto i:r) R.push_back(i);
    for(auto i:v) V.push_back(i);
    N = C.size();
    Q = L.size();
    debug(Q)
    debug(N)
    vector<int32_t> res(N, 0);
    seggs1 = new kadane(0, Q + 5); //normal
    seggs2 = new kadane(0, Q + 5); //negated
    seggs3 = new node(0, Q + 5); //prefixsum
    vector<int> add[N + 5];
    vector<int> remove[N + 5];
    for(int i=0;i<Q;i++){
        add[L[i]].push_back(i);
        remove[R[i]+1].push_back(i);
    }
    for(int i=0;i<N;i++){
        debug(i)
        debug(add[i].size())
        for(auto j:add[i]){
            debug("add")
            debug(j)
            seggs1->upd(j+1, V[j]);
            seggs2->upd(j+1, -V[j]);
            seggs3->upd(j+1, Q, V[j]);
        }
        for(auto j:remove[i]){
            debug("remove")
            debug(j)
            seggs1->upd(j+1, 0);
            seggs2->upd(j+1, 0);
            seggs3->upd(j+1, Q, -V[j]);
        }
        debug("stuff")
        int lastmax = -1;
        int lastmin = 0;
        int lb = 1;
        int ub = Q;
        while(ub > lb){
            debug(ub)
            debug(lb)
            int mid = (ub + lb + 1) >> 1;
            debug(seggs1->query(mid, Q)->maxsum)
            if(seggs1->query(mid, Q)->maxsum >= C[i]) lb = mid;
            else ub = mid - 1;
        }
        debug(seggs1->query(lb, Q)->maxsum)
        if(seggs1->query(lb, Q)->maxsum >= C[i]) lastmax = seggs1->query(lb, Q)->endidx;
        lb = 1;
        ub = Q;
        while(ub > lb){
            debug(ub)
            debug(lb)
            int mid = (ub + lb + 1) >> 1;
            if(seggs2->query(mid, Q)->maxsum >= C[i]) lb = mid;
            else ub = mid - 1;
        }
        debug(lb)
        if(seggs2->query(lb, Q)->maxsum >= C[i]) lastmin = seggs2->query(lb, Q)->endidx;
        debug(lastmax)
        debug(lastmin)
        if(lastmax > lastmin){
            int k = C[i] + seggs3->range_max(Q, Q) - seggs3->range_max(lastmax, Q);
            debug(k)
            debug(i)
            debug(seggs3->range_max(Q, Q))
            debug(seggs3->range_max(lastmax, Q))
            res[i] = k;
        }
        else{
            int k = seggs3->range_max(Q, Q) - seggs3->range_min(lastmin, Q);
            debug(k)
            debug(i)
            debug(seggs3->range_max(Q, Q))
            debug(seggs3->range_min(lastmin, Q))
            res[i] = k;
        }

    }
    return res;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33