Submission #804737

#	Time	Username	Problem	Language	Result	Execution time	Memory
804737		t6twotwo	Distributing Candies (IOI21_candies)	C++17	0 / 100	1240 ms	76268 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e18;
vector<ll> mn, mn2, mx, mx2, lzad, lzmn, lzmx;
void apply_add(int p, ll v) {
    if (p >= mn.size()) {
        return;
    }
    lzad[p] += v;
    mn[p] += v;
    mx[p] += v;
    if (mn2[p] != inf) {
        mn2[p] += v;
    }
    if (mx2[p] != -inf) {
        mx2[p] += v;
    }
}
void apply_min(int p, ll v) {
    if (p >= mn.size()) {
        return;
    }
    if (mn[p] == mx[p]) {
        if (v < mn[p]) {
            mn[p] = mx[p] = v;
            lzmn[p] = v;
        }
    } else if (mx2[p] < v && v < mx[p]) {
        mx[p] = v;
        lzmn[p] = v;
    }
}
void apply_max(int p, ll v) {
    if (p >= mn.size()) {
        return;
    }
    if (mn[p] == mx[p]) {
        if (v > mn[p]) {
            mn[p] = mx[p] = v;
            lzmx[p] = v;
        }
    } else if (mn[p] < v && v < mn2[p]) {
        mn[p] = v;
        lzmx[p] = v;
    }
}
void push_add(int p) {
    apply_add(p * 2, lzad[p]);
    apply_add(p * 2 + 1, lzad[p]);
    lzad[p] = 0;
}
void push_min(int p) {
    apply_min(p * 2, lzmn[p]);
    apply_min(p * 2 + 1, lzmn[p]);
    lzmn[p] = inf;
}
void push_max(int p) {
    apply_max(p * 2, lzmx[p]);
    apply_max(p * 2 + 1, lzmx[p]);
    lzmx[p] = -inf;
}
void pull(int p) {
    int l = p * 2;
    int r = p * 2 + 1;
    mx[p] = max(mx[l], mx[r]);
    mn[p] = min(mn[l], mn[r]);
    mx2[p] = max(mx[p] == mx[l] ? mx2[l] : mx[l], mx[p] == mx[r] ? mx2[r] : mx[r]);
    mn2[p] = min(mn[p] == mn[l] ? mn2[l] : mn[l], mn[p] == mn[r] ? mn2[r] : mn[r]);
}
void add(int p, int l, int r, int L, int R, int v) {
    push_add(p);
    push_min(p);
    push_max(p);
    if (R <= l || r <= L) {
        return;
    }
    if (L <= l && r <= R) {
        apply_add(p, v);
        return;
    }
    int m = (l + r + 1) / 2;
    add(p * 2, l, m, L, R, v);
    add(p * 2 + 1, m, r, L, R, v);
    pull(p);
}
void upd(int p, int l, int r, int L, int R, ll v, bool f) {
    push_add(p);
    push_min(p);
    push_max(p);
    if (R <= l || r <= L || (!f && v >= mx[p]) || (f && v <= mn[p])) {
        return;
    }
    if (L <= l && r <= R && (mn[p] == mx[p] || (!f && v > mx2[p]) || (f && v < mn2[p]))) {
        if (f) {
            apply_max(p, v);
        } else {
            apply_min(p, v);
        }
        return;
    }
    int m = (l + r + 1) / 2;
    upd(p * 2, l, m, L, R, v, f);
    upd(p * 2 + 1, m, r, L, R, v, f);
    pull(p);
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int N = C.size(), Q = V.size();
    int M = 2 << __lg(N - 1);
    mn.resize(2 * M, 0);
    mx.resize(2 * M, 0);
    mn2.resize(2 * M, inf);
    mx2.resize(2 * M, -inf);
    lzad.resize(2 * M);
    lzmn.resize(2 * M, inf);
    lzmx.resize(2 * M, -inf);
    for (int i = 0; i < Q; i++) {
        add(1, 0, M, L[i], R[i] + 1, V[i]);
        if (V[i] > 0) {
            upd(1, 0, M, L[i], R[i] + 1, C[0], 0);
        } else {
            upd(1, 0, M, L[i], R[i] + 1, 0, 1);
        }
    }
    for (int i = 1; i < M; i++) {
        int cnt = 0;
        cnt += lzad[i] != 0;
        cnt += lzmn[i] != inf;
        cnt += lzmx[i] != -inf;
        assert(cnt <= 1);
        push_add(i);
        push_min(i);
        push_max(i);
    }
    vector<int> ans(N);
    for (int i = 0; i < N; i++) {
        ans[i] = mx[i + M];
    }
    return ans;
}

Compilation message (stderr)

candies.cpp: In function 'void apply_add(int, ll)':
candies.cpp:8:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     if (p >= mn.size()) {
      |         ~~^~~~~~~~~~~~
candies.cpp: In function 'void apply_min(int, ll)':
candies.cpp:22:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if (p >= mn.size()) {
      |         ~~^~~~~~~~~~~~
candies.cpp: In function 'void apply_max(int, ll)':
candies.cpp:36:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if (p >= mn.size()) {
      |         ~~^~~~~~~~~~~~

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