#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;
const int maxc = 1E9 + 5;
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<int> C, 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;
}
void Pull(int idx) {
/// no need (?) ///
return;
}
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];
}
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), C.eb(maxc), V.eb(0);
int N = _C.size(), Q = _V.size();
vector<pii> idx_C;
for (int i = 0; i < N; ++i) C.eb(_C[i]), idx_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)), sort(ALL(idx_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]) {
RangeModify(0, N, -1, i); continue;
}
while (lo < hi) {
mi = lo + hi >> 1;
if (CheckVal(mi, i-1) + V[i] >= C[mi]) 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";
}
// cout << "\n";
vector<int> ans(N);
for (int i = 1; i <= N; ++i) {
int tmp_val = CheckVal(i, Q); // cout << tmp_val << "\n";
ans[idx_C[i-1].Y] = tmp_val;
}
return ans;
}
Compilation message
candies.cpp: In function 'void {anonymous}::PointModify(int, int, int, int, int)':
candies.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int nM = nL + nR >> 1;
| ~~~^~~~
candies.cpp: In function 'void {anonymous}::RangeModify(int, int, int, int, int, int, int)':
candies.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | 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:109:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | mi = lo + hi >> 1;
| ~~~^~~~
candies.cpp:123:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
123 | mi = lo + hi >> 1;
| ~~~^~~~
candies.cpp: In function 'int {anonymous}::CheckVal(int, int)':
candies.cpp:54:16: warning: control reaches end of non-void function [-Wreturn-type]
54 | deque<int> stk;
| ^~~
candies.cpp: At global scope:
candies.cpp:48:6: warning: 'void {anonymous}::Pull(int)' defined but not used [-Wunused-function]
48 | void Pull(int idx) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8396 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
8396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
356 ms |
19716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8396 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8524 KB |
Output is correct |
| 3 |
Correct |
638 ms |
14956 KB |
Output is correct |
| 4 |
Correct |
146 ms |
13152 KB |
Output is correct |
| 5 |
Correct |
1143 ms |
19760 KB |
Output is correct |
| 6 |
Correct |
1167 ms |
21000 KB |
Output is correct |
| 7 |
Correct |
1153 ms |
21000 KB |
Output is correct |
| 8 |
Correct |
1246 ms |
21000 KB |
Output is correct |
| 9 |
Correct |
966 ms |
21000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8396 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
8396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
