제출 #524514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524514		Aldas25	사탕 분배 (IOI21_candies)	C++17	11 / 100	1622 ms	75640 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;

const int MAXN = 800100;
const ll INF = 1e10;

int n, q;
ll treeMn[MAXN], treeMx[MAXN], lazy[MAXN];

void shift (int id) {
    ll d = lazy[id];
    lazy[id] = 0;

    treeMn[2*id] += d;
    treeMn[2*id+1] += d;

    treeMx[2*id] += d;
    treeMx[2*id+1] += d;

    lazy[2*id] += d;
    lazy[2*id+1] += d;
}

void upd (int x, int y, ll d, int id = 1, int le = 0, int ri = q) {
    if (x > ri || y < le) return;
    if (x <= le && ri <= y) {
        treeMn[id] += d;
        treeMx[id] += d;
        lazy[id] += d;
        return;
    }

    shift (id);
    int m = (le+ri)/2;
    upd (x, y, d, 2*id, le, m);
    upd (x, y, d, 2*id+1, m+1, ri);

    treeMn[id] = min (treeMn[2*id], treeMn[2*id+1]);
    treeMx[id] = max (treeMx[2*id], treeMx[2*id+1]);
}

ll getMin (int x, int y, int id = 1, int le = 0, int ri = q) {
    if (x > ri || y < le) return INF;
    if (x <= le && ri <= y) return treeMn[id];
    shift (id);
    int m = (le+ri)/2;
    return min(getMin(x, y, 2*id, le, m), getMin(x, y, 2*id+1, m+1, ri));
}

ll getMax (int x, int y, int id = 1, int le = 0, int ri = q) {
    if (x > ri || y < le) return (-INF);
    if (x <= le && ri <= y) return treeMx[id];
    shift (id);
    int m = (le+ri)/2;
    return max(getMax(x, y, 2*id, le, m), getMax(x, y, 2*id+1, m+1, ri));
}

ll c[MAXN];
vi queriesAdd[MAXN], queriesRem[MAXN];
ll l[MAXN], r[MAXN], v[MAXN];

vi distribute_candies(vi _c, vi _l, vi _r, vi _v) {
    n = _c.size();
    q = _l.size();
    vi s(n);

    FOR(i, 0, n-1) c[i] = _c[i];

    l[0] = 0, r[0] = n-1, v[0] = +INF;
    l[1] = 0, r[1] = n-1, v[1] = -INF;
    FOR(i, 0, q-1) {
        l[i+2] = _l[i];
        r[i+2] = _r[i];
        v[i+2] = _v[i];
    }
    q+=2;

    FOR(i, 0, q-1) {
        queriesAdd[l[i]].pb(i);
        queriesRem[r[i]+1].pb(i);
    }

    FOR(i, 0, n-1) {
        //cout << " i = " << i << endl;

        for (int id : queriesAdd[i]) {
          //      cout << "    adding query id = " << id << " v = " << v[id] << endl;
            upd(id, q, v[id]);
        }
        for (int id : queriesRem[i]) {
            //    cout << "    removing query id = " << id << " v = " << v[id] << endl;
            upd (id, q, -v[id]);
        }

        int le = 0, ri = q;
        while (le < ri) {
            int m = (le+ri+1)/2;
            if (getMax(m, q) - getMin(m, q) >= c[i])
                le = m;
            else
                ri = m-1;
        }

        ll mx = getMax(le, q);
        ll mn = getMin(le, q);
        ll lst = getMax(q, q);

        ll mx2 = getMax(le+1, q);

        //cout << "    le = " << le << " mx = " << mx << " mn = " << mn << " lst = " << lst << " mx2 = " << mx2 << endl;

        if (mx == mx2) {
            /// the last touch was to upper wall
            s[i] =(int) (lst - (mx-c[i]));
        } else {
            s[i] = (int) (lst - mn);
        }
    }

    return s;
}

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