Submission #1069452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069452		GusterGoose27	Distributing Candies (IOI21_candies)	C++17	8 / 100	254 ms	49612 KiB

candies

#include "candies.h"

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

const int MAXN = 2e5+5;
const int SEG = 262144;
typedef long long ll;
const ll inf = 1e18;

struct seg_info {
    ll mn_pre, mx_pre, mn_sum, mx_sum, sum;
    seg_info() {
        mn_pre = 0;
        mx_pre = 0;
        mn_sum = 0;
        mx_sum = 0;
        sum = 0;
    }
    seg_info(seg_info l, seg_info r) {
        reupd(l, r);
    }
    void reupd(seg_info &l, seg_info &r) {
        mn_pre = min(l.mn_pre, l.sum+r.mn_pre);
        mx_pre = max(l.mx_pre, l.sum+r.mx_pre);
        mn_sum = min(min(l.mn_sum, r.mn_sum), r.mn_sum + l.sum - l.mx_pre);
        mx_sum = max(max(l.mx_sum, r.mx_sum), r.mx_sum + l.sum - l.mn_pre);
        sum = l.sum + r.sum;
    }
    void upd(int v) {
        mn_pre = min(0, v);
        mx_pre = max(0, v);
        mn_sum = mn_pre;
        mx_sum = mx_pre;
        sum = v;
    }
};

seg_info stree[2*SEG];

seg_info collect(int l, int r) { // inclusive
    l += SEG;
    r += SEG+1;
    seg_info li, ri;
    for (; r > l; l /= 2, r /= 2) {
        if (l & 1) {
            li = seg_info(li, stree[l++]);
        }
        if (r & 1) {
            ri = seg_info(stree[--r], ri);
        }
    }
    return seg_info(li, ri);
}

void upd(int p, int v) {
    p += SEG;
    stree[p].upd(v);
    for (p /= 2; p > 0; p /= 2) {
        stree[p].reupd(stree[2*p], stree[2*p+1]);
    }
}

seg_info violate_pos(int v, int cur = 1, seg_info r_info = seg_info()) {
    if (cur >= SEG) return seg_info(stree[cur], r_info);
    seg_info rcomb(stree[2*cur+1], r_info);
    if (max(rcomb.mx_sum, -rcomb.mn_sum) > v) return violate_pos(v, 2*cur+1, r_info);
    return violate_pos(v, 2*cur, rcomb);
}

int get_final(int v) {
    if (max(stree[1].mx_sum, -stree[1].mn_sum) <= v) return stree[1].sum-stree[1].mn_sum;
    seg_info viol_info = violate_pos(v);
    if (viol_info.mx_sum > v) return v+viol_info.sum-viol_info.mx_sum;
    else return viol_info.sum-viol_info.mn_sum;
}

vector<int> ins[MAXN];
vector<int> del[MAXN];

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n = c.size();
    int q = l.size();
    vector<int> ans;
    for (int i = 0; i < q; i++) {
        ins[l[i]].push_back(i);
        del[r[i]+1].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j: ins[i]) upd(j, v[j]);
        for (int j: del[i]) upd(j, 0);
        ans.push_back(get_final(c[i]));
    }
    return ans;
}

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