#include "candies.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
namespace {
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1 << 18;
struct SegmentTree {
int tag, val, last_change; /// tag is for range modify, val has no use if is not leaf
char last_type;
SegmentTree() {tag = 1, last_change = 0, last_type = 'E';}
};
SegmentTree seg[maxn*2];
vector<pii> C;
vector<int> V, pre_V;
void PushTag(int idx) {
if (seg[idx].tag == 1) return;
seg[idx<<1].tag = seg[idx<<1|1].tag = seg[idx].tag;
if (seg[idx].tag == 0) seg[idx<<1].last_type = seg[idx<<1|1].last_type = 'E';
if (seg[idx].tag == -1) seg[idx<<1].last_type = seg[idx<<1|1].last_type = 'F';
seg[idx<<1].last_change = seg[idx<<1|1].last_change = seg[idx].last_change;
seg[idx].tag = 1;
}
int CheckVal(int idx, int qID) {
deque<int> stk;
int goal = idx + maxn;
while (goal > 1) stk.eb(goal >>= 1);
while (!stk.empty()) PushTag(stk.back()), stk.pb();
goal = idx + maxn;
/// pre_V[qID+1] - pre_V[last_change] ///
// cout << seg[goal].last_type << " " << seg[goal].last_change << ": ";
if (seg[goal].last_type == 'E') return pre_V[qID] - pre_V[seg[goal].last_change];
if (seg[goal].last_type == 'F') return pre_V[qID] - pre_V[seg[goal].last_change] + C[idx].X;
}
void PointModify(int qX, int val, int now = 1, int nL = 0, int nR = maxn-1) {
if (nL == nR) return seg[now].val = val, void();
PushTag(now);
int nM = nL + nR >> 1;
if (qX <= nM) PointModify(qX, val, now<<1, nL, nM);
else PointModify(qX, val, now<<1|1, nM+1, nR);
}
void RangeModify(int qL, int qR, int val, int qID, int now = 1, int nL = 0, int nR = maxn-1) {
if (qL <= nL and nR <= qR) {
seg[now].tag = seg[now].val = val;
seg[now].last_change = qID;
seg[now].last_type = val == 0 ? 'E' : 'F';
return;
}
if (qR < nL or nR < qL) return;
PushTag(now);
int nM = nL + nR >> 1;
RangeModify(qL, qR, val, qID, now<<1, nL, nM);
RangeModify(qL, qR, val, qID, now<<1|1, nM+1, nR);
}
} /// end of namespace
vector<int> distribute_candies(vector<int> _C, vector<int> L, vector<int> R, vector<int> _V) {
C.eb(0, -1), V.eb(0);
int N = _C.size(), Q = _V.size();
for (int i = 0; i < N; ++i) C.eb(_C[i], i);
for (auto &x : _V) V.eb(x);
pre_V.assign(Q+1, 0), partial_sum(ALL(V), begin(pre_V));
sort(ALL(C));
for (int i = 1; i <= Q; ++i) {
// cout << "\n======\n";
// for (int j = 0; j <= N; ++j) cout << CheckVal(j, i-1) << "\n";
// cout << "======\n";
int lo = 0, hi = N, mi;
if (V[i] > 0) {
/// nothing or full ///
if (CheckVal(N, i-1) + V[i] >= C[N].X) {
RangeModify(0, N, -1, i); continue;
}
while (lo < hi) {
mi = lo + hi >> 1;
if (CheckVal(mi, i-1) + V[i] >= C[mi].X) lo = mi + 1; /// [0, mi] is full
else hi = mi; /// [mi, N] is not full
}
/// [0, lo) is full ///
PointModify(lo, CheckVal(lo, i-1) - CheckVal(lo-1, i-1));
RangeModify(0, lo-1, -1, i);
}
else {
/// nothing or empty ///
if (CheckVal(N, i-1) + V[i] <= 0) {
RangeModify(0, N, 0, i); continue;
}
while (lo < hi) {
mi = lo + hi >> 1;
if (CheckVal(mi, i-1) + V[i] <= 0) lo = mi + 1; /// [0, mi] is empty
else hi = mi; /// [mi, N] is not empty
}
/// [0, lo) is empty ///
PointModify(lo, CheckVal(lo, i-1) - CheckVal(lo-1, i-1));
RangeModify(0, lo-1, 0, i);
}
// cout << "\nbinary search gets " << lo << "\n";
}
vector<int> ans(N);
for (int i = 1; i <= N; ++i) ans[C[i-1].Y] = CheckVal(i, Q);
return ans;
}
Compilation message
candies.cpp: In function 'void {anonymous}::PointModify(int, int, int, int, int)':
candies.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int nM = nL + nR >> 1;
| ~~~^~~~
candies.cpp: In function 'void {anonymous}::RangeModify(int, int, int, int, int, int, int)':
candies.cpp:77:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int nM = nL + nR >> 1;
| ~~~^~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:103:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
103 | mi = lo + hi >> 1;
| ~~~^~~~
candies.cpp:117:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
117 | mi = lo + hi >> 1;
| ~~~^~~~
candies.cpp: In function 'int {anonymous}::CheckVal(int, int)':
candies.cpp:49:16: warning: control reaches end of non-void function [-Wreturn-type]
49 | deque<int> stk;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
16972 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
344 ms |
33140 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
17100 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
17004 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
16972 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
