#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 1e9
#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);
}
}
int qqq(int L, int R, int x) {
if(L == R) return tag[get(L, R)] + mx[get(L, R)].first;
else {
push(L, R);
int mid = (L + R) / 2;
if(x <= mid) return qqq(L, mid, x);
else return qqq(mid + 1, R, x);
}
}
pii 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));
if(big.second >= -sm.second) return {big.first, 1};
else return {sm.first, 0};
}
else {
push(L, R);
ll rmx = max(big, get_pii(r, 1)).first;
ll rmn = min(sm, get_pii(r, 0)).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);}
pii query(ll c) { return bs(1, n, c, {-2 * INF, -2 * INF}, {2 * INF, 2 * 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 + 3);
seg::change(1, -INF);
seg::change(2, 2 * INF);
seg::change(3, -INF);
rep(i, 4, m + 3) seg::change(i, v[i - 4]), sum += (ll)v[i - 4];
rep(i, 0, n - 1) {
pii cur = seg::query(c[i]);
if(cur.second) ans[i] = c[i] + sum - cur.first;
else ans[i] = sum - cur.first;
}
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 'std::pair<long long int, 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:95:7: warning: unused variable 'l' [-Wunused-variable]
95 | int l = get(L, mid), r = get(mid + 1, R);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
304 ms |
23108 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 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
185 ms |
20564 KB |
Output is correct |
| 4 |
Correct |
94 ms |
2868 KB |
Output is correct |
| 5 |
Correct |
305 ms |
22968 KB |
Output is correct |
| 6 |
Correct |
308 ms |
23236 KB |
Output is correct |
| 7 |
Incorrect |
286 ms |
23012 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
