oj.uz

Submission #768382

# Submission time Handle Problem Language Result Execution time Memory
768382 2023-06-28T03:41:09 Z PurpleCrayon Distributing Candies (IOI21_candies) C++17
37 / 100
 432 ms 60384 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 1e9+7;

int ans[N];
vector<int> t[4 * N];

void upd(int v, int tl, int tr, int l, int r, int x) {
    if (r < tl || l > tr) return;
    if (l <= tl && tr <= r) {
        t[v].push_back(x);
        return;
    }

    int tm = (tl + tr) / 2;
    upd(2*v, tl, tm, l, r, x), upd(2*v+1, tm+1, tr, l, r, x);
}

vector<int> st; // changes
vector<ll> ps;
vector<pair<ll, int>> bounds;

ll sum(int l, int r) {
    if (r < l) return 0;
    return ps[r] - (l ? ps[l-1] : 0);
}

vector<vector<pair<ll, int>>> save;

int extreme(int i) {
    return i < 0 || st[i] < 0 ? 0 : 1;
}

void push(int x) {
    st.push_back(x);
    ps.push_back((sz(ps) ? ps.back() : 0) + x);

    save.push_back(bounds);
    while (sz(bounds) >= 2) {
        int use = bounds.end()[-2].second;
        ll c = bounds.back().first + 1;
        ll start = extreme(use) * c;
        start += sum(use + 1, sz(st) - 1);
        if (start < 0 || start >= c) {
            bounds.pop_back();
        } else {
            break;
        }
    }

    ll delta = sum(bounds.back().second + 1, sz(st) - 1); 
    int type = extreme(bounds.back().second);
    if (delta <= 0 && type == 0) {
        bounds.back().second = sz(st) - 1;
    } else if (delta >= 0 && type == 1) {
        bounds.back().second = sz(st) - 1;
    } else {
        bounds.emplace_back(abs(delta), sz(st) - 1);
    }
}

// find the max c[i] that makes this last
void undo() {
    bounds = save.back();
    save.pop_back();

    st.pop_back();
    ps.pop_back();
}

int qry(int x) {
    int lo = -1, hi = sz(bounds), mid = (lo + hi) / 2;
    while (lo < mid && mid < hi) {
        if (bounds[mid].first >= x) lo = mid;
        else hi = mid;
        mid = (lo + hi) / 2;
    }

    return extreme(bounds[lo].second) * x + sum(bounds[lo].second + 1, sz(st) - 1);
}

void rec(int v, int tl, int tr, vector<int>& cap) {
    for (int x : t[v]) {
        push(x);
    }

    if (tl == tr) {
        ans[tl] = qry(cap[tl]);
    } else {
        int tm = (tl + tr) / 2;
        rec(2*v, tl, tm, cap);
        rec(2*v+1, tm+1, tr, cap);
    }

    for (int x : t[v]) {
        undo();
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = sz(c), q = sz(v);
    for (int i = 0; i < q; i++) {
        upd(1, 0, n-1, l[i], r[i], v[i]);
    }

    bounds.emplace_back(MOD, -1);
    rec(1, 0, n-1, c);
    return vector<int>(ans, ans + n);
}

Compilation message

candies.cpp: In function 'void rec(int, int, int, std::vector<int>&)':
candies.cpp:100:14: warning: unused variable 'x' [-Wunused-variable]
  100 |     for (int x : t[v]) {
      |              ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Incorrect 8 ms 19028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 56280 KB Output is correct
2 Correct 415 ms 60384 KB Output is correct
3 Correct 432 ms 60296 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 9 ms 19104 KB Output is correct
3 Correct 80 ms 55840 KB Output is correct
4 Correct 50 ms 22520 KB Output is correct
5 Correct 117 ms 60024 KB Output is correct
6 Correct 118 ms 58960 KB Output is correct
7 Correct 122 ms 58072 KB Output is correct
8 Correct 122 ms 59960 KB Output is correct
9 Correct 104 ms 43332 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Incorrect 8 ms 19028 KB Output isn't correct
3 Halted 0 ms 0 KB -