#include "candies.h"
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 2e5 + 10;
const ll inf = 1e18;
int n, q, c[maxn];
vector<pii> Q[maxn];
pll seg[maxn << 2];
ll lazy[maxn << 2];
pll operator +(pll a, pll b){
return MP(min(a.F, b.F), max(a.S, b.S));
}
void shift(int v, int l, int r);
void add(int v, int l, int r, int ql, int qr, ll val){
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
seg[v].F += val;
seg[v].S += val;
lazy[v] += val;
return;
}
shift(v, l, r);
int mid = (l + r) >> 1;
add(v << 1, l, mid, ql, qr, val);
add(v << 1 | 1, mid, r, ql, qr, val);
seg[v] = seg[v << 1] + seg[v << 1 | 1];
}
int find(int v, int l, int r, int val, pll &suf){
//debug(v, l, r, val, seg[v].S, suf.S, seg[v].F, suf.F);
if (max(seg[v].S, suf.S) - min(seg[v].F, suf.F) < val){
suf = suf + seg[v];
return -1;
}
if (l + 1 == r){
suf = suf + seg[v];
return l;
}
shift(v, l, r);
int mid = (l + r) >> 1;
int res = find(v << 1 | 1, mid, r, val, suf);
if (res == -1) res = find(v << 1, l, mid, val, suf);
return res;
}
pii find2(int v, int l, int r, int ql, int qr, pll val){
if (qr <= l || r <= ql) return {-1, 0};
if (ql <= l && r <= qr && seg[v].F > val.F && seg[v].S < val.S) return {-1, 0};
if (l + 1 == r){
pii ret = {l, 0};
if (seg[v].S == val.S) ret.S = 1;
return ret;
}
shift(v, l, r);
int mid = (l + r) >> 1;
pii res = find2(v << 1, l, mid, ql, qr, val);
if (res.F == -1) res = find2(v << 1 | 1, mid, r, ql, qr, val);
return res;
}
int get(int v, int l, int r, int idx){
if (l + 1 == r) return seg[v].F;
shift(v, l, r);
int mid = (l + r) >> 1;
if (idx < mid) return get(v << 1, l, mid, idx);
return get(v << 1 | 1, mid, r, idx);
}
void shift(int v, int l, int r){
if (!lazy[v]) return;
int mid = (l + r) >> 1;
add(v << 1, l, mid, l, mid, lazy[v]);
add(v << 1 | 1, mid, r, mid, r, lazy[v]);
lazy[v] = 0;
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V){
n = C.size();
q = L.size();
for (int i = 0; i < n; i++){
c[i] = C[i];
}
for (int i = 0; i < q; i++){
Q[L[i]].push_back({i, V[i]});
Q[R[i]+1].push_back({i, -V[i]});
}
vector<int> ans(n);
for (int i = 0; i < n; i++){
for (auto [x, y]: Q[i]){
// debug(x, y);
add(1, 0, q, x, q, y);
}
pll tmp = {inf, -inf};
int idx = find(1, 0, q, c[i], tmp);
// debug(i, idx);
pii idx2 = find2(1, 0, q, idx+1, q, tmp);
// debug(idx2.F, idx2.S);
ans[i] = get(1, 0, q, q) - get(1, 0, q, idx2.F);
if (idx2.S == 1) ans[i] += c[i];
// debug(ans[i]);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
463 ms |
37024 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 |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
