#include "candies.h"
#include <bits/stdc++.h>
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;
int n, q, a[maxn], c[maxn], f[maxn];
pll seg[maxn << 2];
pll lazy[maxn << 2];
void add(int idx, int x){
for (; idx <= q; idx += idx & -idx) f[idx] += x;
}
int get(int idx){
int res = 0;
for (; idx; idx -= idx & -idx) res += f[idx];
return res;
}
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 (v == 1) debug(ql, qr, val);
// debug(v, l, r, ql, qr, val);
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
seg[v].F += val;
seg[v].S += val;
lazy[v].F += 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];
}
void reverse(int v, int l, int r, int ql, int qr){
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
swap(seg[v].F, seg[v].S);
seg[v].F = -seg[v].F;
seg[v].S = -seg[v].S;
lazy[v].F = -lazy[v].F;
lazy[v].S *= -1;
return;
}
shift(v, l, r);
int mid = (l + r) >> 1;
reverse(v << 1, l, mid, ql, qr);
reverse(v << 1 | 1, mid, r, ql, qr);
seg[v] = seg[v << 1] + seg[v << 1 | 1];
}
ll 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);
}
int find(int v, int l, int r, int ql, int qr, ll val){
// debug(v, l, r, seg[v].F, seg[v].S, val);
if (qr <= l || r <= ql) return -1;
if (ql <= l && r <= qr && seg[v].F >= 0 && seg[v].S <= val) return -1;
if (l + 1 == r) return l;
shift(v, l, r);
int mid = (l + r) >> 1;
int res = find(v << 1, l, mid, ql, qr, val);
if (res == -1) res = find(v << 1 | 1, mid, r, ql, qr, val);
return res;
}
void shift(int v, int l, int r){
if (lazy[v].F == 0 && lazy[v].S == 1) return;
int mid = (l + r) >> 1;
if (lazy[v].S != 1){
reverse(v << 1, l, mid, l, mid);
reverse(v << 1 | 1, mid, r, mid, r);
}
if (lazy[v].F != 0){
add(v << 1, l, mid, l, mid, lazy[v].F);
add(v << 1 | 1, mid, r, mid, r, lazy[v].F);
}
lazy[v] = {0, 1};
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
n = C.size();
q = L.size();
vector<pii> num;
for (int i = 0; i < 4*maxn; i++) lazy[i] = {0, 1};
for (int i = 0; i < n; i++){
c[i] = C[i];
num.push_back({c[i], i});
}
set<pii> st;
for (int i = 0; i < q; i++){
add(1, 0, q, i, q, V[i]);
}
st.insert({0, q-1});
sort(all(num), greater<pii>());
for (auto [x, y]: num){
// debug(x, y);
int tmp;
while((tmp = find(1, 0, q, 0, q, x)) != -1){
// debug(tmp);
int val = get(1, 0, q, tmp);
auto it = st.upper_bound({tmp, 0});
it--;
int L = (*it).F;
int R = (*it).S;
st.erase(it);
if (L != tmp) st.insert({L, tmp-1});
st.insert({tmp, R});
add(1, 0, q, tmp, R+1, -val);
if (val > x){
reverse(1, 0, q, tmp, R+1);
add(tmp+1, 1);
}
}
int res = get(1, 0, q, q-1);
a[y] = ((get(q) & 1)? x-res:res);
}
vector<int> ans;
for (int i = 0; i < n; i++){
ans.push_back(a[i]);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
12756 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
12756 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
343 ms |
41884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
25836 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
12756 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
12756 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
