#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()
#define INF 2e9
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#define ll long long int
#define lld long double
#define pii pair<ll, ll>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#ifdef wiwihorz
#define print(a...) cerr << "line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#include "candies.h"
namespace seg {
int n;
vector<ll> tag;
vector<pii> mx, mn;
int get(int L, int R) { return (L + R) | (L != R);}
pii get_pii(int nd, int id) {
if(id == 0) return {mn[nd].first + tag[nd], mn[nd].second};
else return {mx[nd].first + tag[nd], mx[nd].second};
}
void pull(int L, int R) {
int nd = get(L, R), mid = (L + R) / 2;
int l = get(L, mid), r = get(mid + 1, R);
mx[nd] = max(get_pii(l, 1), get_pii(r, 1));
mn[nd] = min(get_pii(l, 0), get_pii(r, 0));
}
void push(int L, int R) {
int nd = get(L, R), mid = (L + R) / 2;
int l = get(L, mid), r = get(mid + 1, R);
tag[l] += tag[nd];
tag[r] += tag[nd];
mn[nd].first += tag[nd];
mx[nd].first += tag[nd];
tag[nd] = 0;
}
void build(int L, int R) {
int nd = get(L, R), mid = (L + R) / 2;
if(L == R) mx[nd] = {0, L}, mn[nd] = {0, -L};
else {
build(L, mid);
build(mid + 1, R);
pull(L, R);
}
}
void init_(int _n) {
n = _n;
tag.assign(2 * n + 1, 0);
mx.assign(2 * n + 1, {0, 0});
mn.assign(2 * n + 1, {0, 0});
build(1, n);
}
void modify(int L, int R, int l, int r, int val) {
int mid = (L + R) / 2, nd = get(L, R);
if(l > R || r < L) return;
if(L != R) push(L, R);
if(l <= L && r >= R) tag[nd] += val;
else {
modify(L, mid, l, r, val);
modify(mid + 1, R, l, r, val);
pull(L, R);
}
}
ll bs(int L, int R, int c, pii big, pii sm) {
int mid = (L + R) / 2, nd = get(L, R);
int l = get(L, mid), r = get(mid + 1, R);
if(L == R) {
big = max(big, get_pii(nd, 1));
sm = min(sm, get_pii(nd, 0));
assert(big.first - sm.first >= c);
if(big.second >= -sm.second) return big.first;
else return sm.first;
}
else {
push(L, R);
ll rmx = max(big.first, tag[r] + mx[r].first);
ll rmn = min(sm.first, tag[r] + mn[r].first);
if(rmx - rmn >= c) return bs(mid + 1, R, c, big, sm);
else return bs(L, mid, c, max(big, get_pii(r, 1)), min(sm, get_pii(r, 0)));
}
}
void change(int x, ll val) { modify(1, n, x, n, val);}
ll query(ll c) { return bs(1, n, c, {-INF, -INF}, {INF, INF});}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(), m = l.size();
ll sum = 0;
vector<int> ans(n, 0);
// 全部都往後墊3
seg::init_(m + 2);
seg::change(1, -INF);
seg::change(2, INF);
rep(i, 3, m + 2) seg::change(i, v[i - 3]), sum += (ll)v[i - 3];
rep(i, 0, n - 1) {
int vv = seg::query(c[i]);print(vv);
if(vv >= sum) ans[i] = c[i] + sum - vv;
else ans[i] = vv - sum;
}
return ans;
}
Compilation message
candies.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
4 | #pragma loop-opt(on)
|
candies.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
| ^~~~
candies.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
| ^~~~
candies.cpp: In function 'long long int seg::bs(int, int, int, std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
candies.cpp:86:7: warning: unused variable 'l' [-Wunused-variable]
86 | int l = get(L, mid), r = get(mid + 1, R);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2831 ms |
29068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
