Submission #1239343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239343		Hamed_Ghaffari	Distributing Candies (IOI21_candies)	C++20	100 / 100	232 ms	36408 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 2e5+5;

int n, q;
ll mx[MXN<<2], mn[MXN<<2], lz[MXN<<2];

inline void apply(ll x, int id) {
    mx[id] += x;
    mn[id] += x;
    lz[id] += x;
}
inline void push(int id) {
    if(lz[id]) {
        apply(lz[id], lc);
        apply(lz[id], rc);
        lz[id] = 0;
    }
}
void upd(int s, int e, ll x, int l=0, int r=q+1, int id=1) {
    if(s>=r || l>=e) return;
    if(s<=l && r<=e) {
        apply(x, id);
        return;
    }
    push(id);
    upd(s, e, x, l, mid, lc);
    upd(s, e, x, mid, r, rc);
    mx[id] = max(mx[lc], mx[rc]);
    mn[id] = min(mn[lc], mn[rc]);
}
ll cmx_, cmn_, val;
int find(ll lb, ll cmx=-1e18, ll cmn=1e18, int l=0, int r=q+1, int id=1) {
    if(max(mx[id], cmx)-min(mn[id], cmn)<lb) return -1;
    if(r-l == 1) { cmx_=max(cmx, mx[id]), cmn_=min(cmn, mn[id]), val=mx[id]; return l; }
    push(id);
    int res = find(lb, cmx, cmn, mid, r, rc);
    return res==-1 ? find(lb, max(cmx, mx[rc]), min(cmn, mn[rc]), l, mid, lc) : res;
}

vector<int> S[MXN], E[MXN];

vector<int> distribute_candies(vector<int> c, vector<int> lq, vector<int> rq, vector<int> vq) {
    n = c.size(), q = lq.size();
    for(int i=0; i<q; i++) {
        S[lq[i]].push_back(i);
        E[rq[i]+1].push_back(i);
    }
    ll tot = 0;
    vector<int> ans(n);
    for(int i=0; i<n; i++) {
        for(int j : S[i]) tot += vq[j], upd(j+1, q+1, vq[j]);
        for(int j : E[i]) tot -= vq[j], upd(j+1, q+1, -vq[j]);
        int wh = find(c[i]);
        if(wh==-1) ans[i] = tot-mn[1];
        else ans[i] = val==cmx_ ? tot-cmn_ : tot-cmx_+c[i];
    }
    return ans;
}

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