#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll int, ll int>
#define ff first
#define ss second
const int mxN = 2e5 + 10;
const ll int MAX = 1e18, MIN = -1e18;
pll seg[4 * mxN]; // {min, max}
ll int lazy[4 * mxN];
bool marked[4 * mxN];
vector<pii> queries[mxN]; // {pos, val};
int n, q;
void pushdown(int idx) {
if (marked[idx]) {
seg[(idx << 1)].ff += lazy[idx];
seg[(idx << 1)].ss += lazy[idx];
seg[(idx << 1) | 1].ff += lazy[idx];
seg[(idx << 1) | 1].ss += lazy[idx];
lazy[(idx << 1)] += lazy[idx];
lazy[(idx << 1) | 1] += lazy[idx];
lazy[idx] = 0;
marked[(idx << 1)] = true;
marked[(idx << 1) | 1] = true;
marked[idx] = false;
}
}
void update(int tl, int tr, ll int val, int l = 0, int r = q, int idx = 1) {
cerr << "Seg Update: " << l << ' ' << r << ' ' << idx << ' ' << val << endl;
if (tl <= l && r <= tr) {
seg[idx].ff += val;
seg[idx].ss += val;
lazy[idx] += val;
marked[idx] = true;
return;
}
pushdown(idx);
int mid = (l + r) >> 1;
if (tl <= mid) update(tl, min(tr, mid), l, mid, (idx << 1));
if (tr > mid) update(max(tl, mid + 1), tr, mid + 1, r, (idx << 1) | 1);
seg[idx].ff = min(seg[(idx << 1)].ff, seg[(idx << 1) | 1].ff);
seg[idx].ss = max(seg[(idx << 1)].ss, seg[(idx << 1) | 1].ss);
}
pll query(int tl, int tr, int l = 0, int r = q, int idx = 1) {
if (tl <= l && r <= tr) return seg[idx];
pushdown(idx);
int mid = (l + r) >> 1;
pll ret = {MAX, MIN}, take;
if (tl <= mid) {
take = query(tl, min(tr, mid), l, mid, (idx << 1));
ret.ff = min(ret.ff, take.ff);
ret.ss = max(ret.ss, take.ss);
}
if (tr > mid) {
take = query(max(tl, mid + 1), tr, mid + 1, r, (idx << 1) | 1);
ret.ff = min(ret.ff, take.ff);
ret.ss = max(ret.ss, take.ss);
}
return ret;
}
int descend(int tar, pll &cur, int l = 0, int r = q, int idx = 1) {
if (max(cur.ss, seg[idx].ss) - min(cur.ff, seg[idx].ff) <= tar) {
cur.ff = min(cur.ff, seg[idx].ff);
cur.ss = max(cur.ss, seg[idx].ss);
return -1;
} else if (l == r) return l;
pushdown(idx);
int mid = (l + r) >> 1;
int ret = descend(tar, cur, mid + 1, r, (idx << 1) | 1);
if (ret != -1) return ret;
else return descend(tar, cur, l, mid, (idx << 1));
}
ll int querypos(int tar, int l = 0, int r = q, int idx = 1) {
if (l == r) return seg[idx].ff;
pushdown(idx);
int mid = (l + r) >> 1;
if (tar <= mid) return querypos(tar, l, mid, (idx << 1));
else return querypos(tar, mid + 1, r, (idx << 1) | 1);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size(); q = v.size();
vector<int> fin(n);
for (int i = 0; i < q; i++) {
queries[l[i]].pb({i + 1, v[i]});
queries[r[i] + 1].pb({i + 1, -v[i]});
}
for (int i = 0; i < n; i++) {
for (pii &cur : queries[i]) {
cerr << "Update: " << cur.ff << ' ' << q << ' ' << cur.ss << endl;
update(cur.ff, q, cur.ss);
}
pll range = {MAX, MIN};
int pos = descend(c[i], range);
cerr << i + 1 << ": " << range.ff << ' ' << range.ss << endl;
if (pos == -1) {
fin[i] = range.ss - range.ff;
} else {
ll int val = querypos(pos);
if (val < range.ff) {
fin[i] = c[i] - (range.ss - querypos(q));
} else if (val > range.ss) {
fin[i] = (querypos(q) - range.ff);
}
}
}
return fin;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5046 ms |
39508 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
