/* Ignut
started: 16.08.2024
now: 16.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████ ████████████████████████████████
██████████████████████████████ ██████████████████████████████
██████ ██████████████████ ██████████████████ ██████
██████ ██████████████ ██████████████ ██████
██████ ██ ████████████ ████████████ ██ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ██████ ██████
██████ ██████ ██████████ ██████████ ██████ ██████
██████ ██████ ████████ ████████ ██████ ██████
██████ ██████ ██████ ██████ ██████ ██████
██████ ████ ████ ████ ████ ██████
██████ ██████████ ████ ██████████ ██████
██████ ██ ██████ ████████ ██████ ██ ██████
██████ ██████ ████████ ██████ ██████
██████ ██ ██ ██████
██████████████████████ ████ ████ ██████████████████████
████████████████████████ ██ ██ ████████████████████████
██████████████████████████ ██████████████████████████
██████████████████████████████ ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18 + 123;
const int N = 2e5 + 123;
int q;
// prefix sum segment tree
ll mn[4 * N], mx[4 * N];
vector<ll> p;
void Build(int v, int l, int r) {
if (l == r) {
mx[v] = mn[v] = p[l];
return;
}
int mid = l + (r - l) / 2;
Build(v * 2, l, mid), Build(v * 2 + 1, mid + 1, r);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}
ll Min(int v, int l, int r, int ql, int qr) {
if (l > qr || ql > r)
return INF;
if (l >= ql && r <= qr)
return mn[v];
int mid = l + (r - l) / 2;
return min(Min(v * 2, l, mid, ql, qr), Min(v * 2 + 1, mid + 1, r, ql, qr));
}
ll Min(int l, int r) {
if (l > r) return INF;
return Min(1, 0, q - 1, l, r);
}
ll Max(int v, int l, int r, int ql, int qr) {
if (l > qr || ql > r)
return -INF;
if (l >= ql && r <= qr)
return mx[v];
int mid = l + (r - l) / 2;
return max(Max(v * 2, l, mid, ql, qr), Max(v * 2 + 1, mid + 1, r, ql, qr));
}
ll Max(int l, int r) {
if (l > r) return -INF;
return Max(1, 0, q - 1, l, r);
}
vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v) {
int n = C.size();
q = l.size();
p.push_back(v[0]);
for (int i = 1; i < q; i ++) p.push_back(p.back() + v[i]);
Build(1, 0, q - 1);
vector<int> c = C;
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
reverse(c.begin(), c.end());
int lastPeak = -1;
char peakType = 'd';
int sum = 0;
for (int i = 0; i < q; i ++) {
sum += v[i];
if (sum <= 0) {
lastPeak = i;
peakType = 'd';
sum = 0;
}
if (sum >= c[0]) {
lastPeak = i;
peakType = 'u';
sum = c[0];
}
}
// cout << Min(0, 0) << ' ' << Min(1, 1) << ' ' << Min(2, 2) << '\n';
map<int, int> mp;
for (int cc : c) {
ll before = (lastPeak == -1 ? 0 : p[lastPeak]);
while (true) {
before = (lastPeak == -1 ? 0 : p[lastPeak]);
if (peakType == 'd') {
if (Max(lastPeak + 1, q - 1) - before < cc && Min(lastPeak + 1, q - 1) - before > 0)
break;
}
else {
// cout << Min(lastPeak + 1, q - 1) << '\n';
if (Max(lastPeak + 1, q - 1) - before < 0 && Min(lastPeak + 1, q - 1) - before > -cc)
break;
}
int lo = lastPeak + 1, hi = q - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (peakType == 'd') {
if (Max(lastPeak + 1, lo) - before >= cc || Min(lastPeak + 1, lo) - before <= 0)
hi = mid;
else
lo = mid + 1;
}
else {
if (Max(lastPeak + 1, lo) - before >= 0 || Min(lastPeak + 1, lo) - before <= -cc)
hi = mid;
else
lo = mid + 1;
}
}
int nextPeak = lo;
if (peakType == 'd') {
if (Max(lastPeak + 1, nextPeak) - before >= cc) peakType = 'u';
else peakType = 'd';
}
else {
if (Max(lastPeak + 1, nextPeak) - before >= 0) peakType = 'u';
else peakType = 'd';
}
lastPeak = nextPeak;
}
before = (lastPeak == -1 ? 0 : p[lastPeak]);
// cout << cc << " : " << lastPeak << " -- " << peakType << '\n';
mp[cc] = p[q - 1] - before + (peakType == 'u' ? cc : 0);
}
vector<int> res;
for (int i = 0; i < n; i ++) res.push_back(mp[C[i]]);
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
153 ms |
26520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
