Submission #1126280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126280		Tyx2019	Distributing Candies (IOI21_candies)	C++20	100 / 100	3671 ms	1296868 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define int long long 
#define debug(x) if(0) cout << #x << " is " << x << endl;
#pragma GCC optimise("Ofast");
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;
    mxsubarr* vals;
    kadane *l, *r;
    kadane(int _S, int _E){
        S = _S;
        E = _E;
        M = (S + E) >> 1;
       
            l = r = NULL;
            vals = new mxsubarr(0, 0, 0, 0, S, 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){
            vals = new mxsubarr(val, val, val, val, S, S);
            return;
        }
        if(idx <= M) l->upd(idx, val);
        else r->upd(idx, val);
        vals = merge(l->vals, r->vals);
    }
    int bsta(int goal, mxsubarr* right){
        if(S == E){
            auto k = merge(vals, right);
            return k->endidx;
        }
        auto k = merge(r->vals, right);
        if(k->maxsum >= goal){
            return r->bsta(goal, right);
        }
        else{
            return l->bsta(goal, k);
        }
    }
}*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();
        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;
vector<int32_t> distribute_candies(vector<int32_t> C, vector<int32_t> L, vector<int32_t> R, vector<int32_t> V) {
    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++){

        for(auto j:add[i]){
            seggs1->upd(j+1, V[j]);
            seggs2->upd(j+1, -V[j]);
            seggs3->upd(j+1, Q, V[j]);
        }
        for(auto j:remove[i]){
            seggs1->upd(j+1, 0);
            seggs2->upd(j+1, 0);
            seggs3->upd(j+1, Q, -V[j]);
        }
        int lastmax = -1;
        int lastmin = 0;
        auto k = new mxsubarr(-1000, -1000, -1000, -1000, 69, 69);
        if(seggs1->vals->maxsum >= C[i]) lastmax = seggs1->bsta(C[i], k);
        if(seggs2->vals->maxsum >= C[i]) lastmin = seggs2->bsta(C[i], k);
        if(lastmax > lastmin){
            int k = C[i] + seggs3->range_max(Q, Q) - seggs3->range_max(lastmax, Q);
            res[i] = k;
        }
        else{
            int k = seggs3->range_max(Q, Q) - seggs3->range_min(lastmin, Q);
            res[i] = k;
        }

    }
    return res;
}

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