제출 #531248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531248		alextodoran	사탕 분배 (IOI21_candies)	C++17	100 / 100	386 ms	43020 KiB

candies

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "candies.h"

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

struct SGTNode {
    ll delta;
    ll minVal;
    ll maxVal;
    void setVal (const int &v) {
        delta = v;
        minVal = min((ll) 0, -delta);
        maxVal = max((ll) 0, -delta);
    }
};
SGTNode operator + (const SGTNode &u, const SGTNode &v) {
    SGTNode w;
    w.delta = u.delta + v.delta;
    w.minVal = min(v.minVal, -v.delta + u.minVal);
    w.maxVal = max(v.maxVal, -v.delta + u.maxVal);
    return w;
}

int N;
SGTNode SGT[N_MAX * 4 + 2];

void build (int node, int l, int r) {
    if (l == r) {
        SGT[node].setVal(0);
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(lSon, l, mid);
    build(rSon, mid + 1, r);
    SGT[node] = SGT[lSon] + SGT[rSon];
}
void build (int n) {
    N = n;
    build(1, 1, N);
}
void update (int node, int l, int r, int pos, int val) {
    if (l == r) {
        SGT[node].setVal(val);
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (pos <= mid) {
        update(lSon, l, mid, pos, val);
    } else {
        update(rSon, mid + 1, r, pos, val);
    }
    SGT[node] = SGT[lSon] + SGT[rSon];
}
void update (int pos, int val) {
    update(1, 1, N, pos + 1, val);
}
ll query (int node, int l, int r, ll currMin, ll currMax, int diff) {
    if (l == r) {
        ll excess = max((ll) 0, (max(currMax, SGT[node].maxVal) - min(currMin, SGT[node].minVal)) - diff);
        if (SGT[node].delta > 0) {
            return +excess;
        } else {
            return -excess - diff;
        }
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    ll minr = min(currMin, SGT[rSon].minVal);
    ll maxr = max(currMax, SGT[rSon].maxVal);
    if (maxr - minr >= diff) {
        return SGT[lSon].delta + query(rSon, mid + 1, r, currMin, currMax, diff);
    } else {
        return query(lSon, l, mid, minr + SGT[rSon].delta, maxr + SGT[rSon].delta, diff);
    }
}
ll query (int diff) {
    return query(1, 1, N, 0, 0, diff);
}

vector <int> distribute_candies (vector <int> c, vector <int> l,
                                 vector <int> r, vector <int> v) {
    int n = (int) c.size();
    int q = (int) v.size();

    vector <int> evAdd[n], evDel[n];
    for (int i = 0; i < q; i++) {
        evAdd[l[i]].push_back(i);
        evDel[r[i]].push_back(i);
    }

    build(2 + q);
    update(0, + (int) 1e9);
    update(1, - (int) 1e9);
    vector <int> answer (n);
    for (int i = 0; i < n; i++) {
        for (int j : evAdd[i]) {
            update(2 + j, v[j]);
        }
        answer[i] = SGT[1].delta - query(c[i]);
        for (int j : evDel[i]) {
            update(2 + j, 0);
        }
    }
    return answer;
}

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