oj.uz

Submission #524514

# Submission time Handle Problem Language Result Execution time Memory
524514 2022-02-09T11:37:52 Z Aldas25 Distributing Candies (IOI21_candies) C++17
11 / 100
 1622 ms 75640 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37836 KB Output is correct
2 Correct 18 ms 37836 KB Output is correct
3 Correct 20 ms 38044 KB Output is correct
4 Correct 20 ms 38076 KB Output is correct
5 Correct 24 ms 38272 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1622 ms 75640 KB Output is correct
2 Correct 1595 ms 74932 KB Output is correct
3 Correct 1589 ms 74668 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37836 KB Output is correct
2 Incorrect 283 ms 65520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37836 KB Output is correct
2 Correct 20 ms 37948 KB Output is correct
3 Correct 129 ms 63920 KB Output is correct
4 Correct 539 ms 43360 KB Output is correct
5 Correct 1308 ms 68888 KB Output is correct
6 Correct 1334 ms 69528 KB Output is correct
7 Incorrect 1289 ms 70184 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37836 KB Output is correct
2 Correct 18 ms 37836 KB Output is correct
3 Correct 20 ms 38044 KB Output is correct
4 Correct 20 ms 38076 KB Output is correct
5 Correct 24 ms 38272 KB Output is correct
6 Correct 1622 ms 75640 KB Output is correct
7 Correct 1595 ms 74932 KB Output is correct
8 Correct 1589 ms 74668 KB Output is correct
9 Correct 21 ms 37836 KB Output is correct
10 Incorrect 283 ms 65520 KB Output isn't correct
11 Halted 0 ms 0 KB -