제출 #1061797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1061797		Ignut	사탕 분배 (IOI21_candies)	C++17	29 / 100	155 ms	31456 KiB

candies

/* Ignut
started: 16.08.2024
now: 16.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e18 + 123;
const int N = 2e5 + 123;
int q;

// prefix sum segment tree
ll mn[4 * N], mx[4 * N];
vector<ll> p;

void Build(int v, int l, int r) {
    if (l == r) {
        mx[v] = mn[v] = p[l];
        return;
    }
    int mid = l + (r - l) / 2;
    Build(v * 2, l, mid), Build(v * 2 + 1, mid + 1, r);
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}

ll Min(int v, int l, int r, int ql, int qr) {
    if (l > qr || ql > r)
        return INF;
    if (l >= ql && r <= qr)
        return mn[v];
    int mid = l + (r - l) / 2;
    return min(Min(v * 2, l, mid, ql, qr), Min(v * 2 + 1, mid + 1, r, ql, qr));
}
ll Min(int l, int r) {
    if (l > r) return INF;
    return Min(1, 0, q - 1, l, r);
}

ll Max(int v, int l, int r, int ql, int qr) {
    if (l > qr || ql > r)
        return -INF;
    if (l >= ql && r <= qr)
        return mx[v];
    int mid = l + (r - l) / 2;
    return max(Max(v * 2, l, mid, ql, qr), Max(v * 2 + 1, mid + 1, r, ql, qr));
}
ll Max(int l, int r) {
    if (l > r) return -INF;
    return Max(1, 0, q - 1, l, r);
}

vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v) {
    int n = C.size();
    q = l.size();
    
    p.push_back(v[0]);
    for (int i = 1; i < q; i ++) p.push_back(p.back() + v[i]);

    Build(1, 0, q - 1);

    vector<int> c = C;
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    reverse(c.begin(), c.end());

    int lastPeak = -1;
    char peakType = 'd';
    int sum = 0;
    for (int i = 0; i < q; i ++) {
        sum += v[i];
        if (sum <= 0) {
            lastPeak = i;
            peakType = 'd';
            sum = 0;
        }
        if (sum >= c[0]) {
            lastPeak = i;
            peakType = 'u';
            sum = c[0];
        }
    }

    // cout << Min(0, 0) << ' ' << Min(1, 1) << ' ' << Min(2, 2) << '\n';

    map<int, int> mp;

    for (int cc : c) {
        ll before = (lastPeak == -1 ? 0 : p[lastPeak]);
        while (true) {
            before = (lastPeak == -1 ? 0 : p[lastPeak]);
            if (peakType == 'd') {
                if (Max(lastPeak + 1, q - 1) - before < cc && Min(lastPeak + 1, q - 1) - before > 0)
                    break;
            }
            else {
                // cout << Min(lastPeak + 1, q - 1) << '\n';
                if (Max(lastPeak + 1, q - 1) - before < 0 && Min(lastPeak + 1, q - 1) - before > -cc)
                    break;
            }

            int lo = lastPeak + 1, hi = q - 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (peakType == 'd') {
                    if (Max(lastPeak + 1, mid) - before >= cc || Min(lastPeak + 1, mid) - before <= 0)
                        hi = mid;
                    else
                        lo = mid + 1;
                }
                else {
                    if (Max(lastPeak + 1, mid) - before >= 0 || Min(lastPeak + 1, mid) - before <= -cc)
                        hi = mid;
                    else
                        lo = mid + 1;
                }
            }

            int nextPeak = lo;
            if (peakType == 'd') {
                if (Max(lastPeak + 1, nextPeak) - before >= cc) peakType = 'u';
                else peakType = 'd';
            }
            else {
                if (Max(lastPeak + 1, nextPeak) - before >= 0) peakType = 'u';
                else peakType = 'd';
            }

            lastPeak = nextPeak;
        }
        before = (lastPeak == -1 ? 0 : p[lastPeak]);
        mp[cc] = p[q - 1] - before + (peakType == 'u' ? cc : 0);
    }

    vector<int> res;
    for (int i = 0; i < n; i ++) res.push_back(mp[C[i]]);
    return res;
}

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