/*
* File created on 06/18/2022 at 11:23:40.
* Link to problem:
* Description: subtask 4 solution
* Time complexity: O(N log^2 N)
* Space complexity: O()
* Status: ---
* Copyright: Ⓒ 2022 Francois Vogel
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define size(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear
#define ll long long
#define ld long double
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int p2 = 1<<18;
struct Segtree {
Segtree() {
lzSet = new bool [p2*2];
for (int i = 0; i < p2*2; i++) lzSet[i] = false;
t = new int [p2*2];
for (int i = 0; i < p2*2; i++) t[i] = 0;
lzAdd = new int [p2*2];
for (int i = 0; i < p2*2; i++) lzAdd[i] = 0;
}
void push(int qn) {
if (lzSet[qn]) {
if (qn < p2) {
lzAdd[qn*2] = lzAdd[qn*2+1] = false;
lzSet[qn*2] = lzSet[qn*2+1] = true;
}
t[qn] = 0;
lzSet[qn] = false;
}
if (lzAdd[qn]) {
if (qn < p2) {
lzAdd[qn*2] += lzAdd[qn];
lzAdd[qn*2+1] += lzAdd[qn];
}
t[qn] += lzAdd[qn];
lzAdd[qn] = 0;
}
}
void set(int rb, int re, int qn = 1, int qb = 0, int qe = p2-1) {
push(qn);
if (rb > qe || qb > re) return;
else if (rb <= qb && qe <= re) {
lzSet[qn] = true;
}
else {
int qm = (qb+qe)/2;
set(rb, re, qn*2, qb, qm);
set(rb, re, qn*2+1, qm+1, qe);
}
}
void add(int rb, int re, int rv, int qn = 1, int qb = 0, int qe = p2-1) {
push(qn);
if (rb > qe || qb > re) return;
else if (rb <= qb && qe <= re) {
lzAdd[qn] += rv;
}
else {
int qm = (qb+qe)/2;
add(rb, re, rv, qn*2, qb, qm);
add(rb, re, rv, qn*2+1, qm+1, qe);
}
}
int get(int r, int qn = 1, int qb = 0, int qe = p2-1) {
push(qn);
if (r == qb && r == qe) return t[qn];
else {
int qm = (qb+qe)/2;
if (r <= qm) return get(r, qn*2, qb, qm);
else return get(r, qn*2+1, qm+1, qe);
}
}
bool* lzSet;
int* t, *lzAdd;
};
vi distribute_candies(vi b, vi queryL, vi queryR, vi queryV) {
int n = size(b);
int nbQ = size(queryL);
vector<pii> sorted;
for (int i = 0; i < n; i++) sorted.pb({b[i], i});
sort(all(sorted));
int posOf [n];
for (int i = 0; i < n; i++) posOf[sorted[i].s] = i;
for (int i = 0; i < n; i++) b[i] = sorted[i].f;
Segtree st [2];
st[0] = Segtree();
st[1] = Segtree();
Segtree use = Segtree();
for (int i : queryV) {
if (i == 0) continue;
int upto = -1;
for (int j = p2; j; j /= 2) if (upto+j < n) {
int loc;
if (use.get(upto+j) == 0) {
loc = st[0].get(upto+j);
loc += i;
}
else {
loc = st[1].get(upto+j);
loc = b[upto+j] - loc;
loc += i;
}
if (!(0 <= loc && loc <= b[upto+j])) {
upto += j;
}
}
st[0].add(0, n-1, i);
st[1].add(0, n-1, -i);
if (upto >= 0) {
if (i < 0) {
st[0].set(0, upto);
use.set(0, upto);
}
else {
st[1].set(0, upto);
use.set(0, upto);
use.add(0, upto, 1);
}
}
// for debug
// for (int j = 0; j < n; j++) {
// cout << use.get(j) << ' ';
// }
// cout << endl;
// int d = 0;
// d++;
// end debug
// for debugging purposes
// for (int j = 0; j < n; j++) {
// int res;
// if (use.get(j) == 0) {
// res = st[0].get(j);
// }
// else {
// res = st[1].get(j);
// res = b[j]-res;
// }
// // assert(0 <= res && res <= b[j]);
// cout << res << ' ';
// }
// cout << endl;
// int d2 = 0;
// d2++;
// end debugging
}
vi ans;
for (int i = 0; i < n; i++) {
int res;
if (use.get(posOf[i]) == 0) {
res = st[0].get(posOf[i]);
}
else {
res = st[1].get(posOf[i]);
res = b[posOf[i]]-res;
}
// assert(0 <= res && res <= b[posOf[i]]);
ans.pb(res);
}
return ans;
}
// signed main() {
// cin.tie(0);
// ios_base::sync_with_stdio(0);
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
// distribute_candies({0, 4}, {}, {}, {9, -3});
// while (1) {
// int n = 5;
// int nbQ = 10;
// int lim = 1e9;
// vi b, q;
// for (int i = 0; i < n; i++) {
// b.pb(rng()%lim);
// }
// for (int i = 0; i < nbQ; i++) q.pb((-lim)+rng()%(2*lim));
// vi ans = distribute_candies(b, q, q, q);
// vi exp(n, 0);
// for (int i : q) {
// for (int j = 0; j < n; j++) {
// exp[j] += i;
// exp[j] = max(exp[j], 0);
// exp[j] = min(exp[j], b[j]);
// }
// }
// for (int i = 0; i < n; i++) {
// if (ans[i] != exp[i]) {
// cout << "WA" << endl;
// cout << "b: ";
// for (int j : b) cout << j << ' ';
// cout << endl;
// cout << "q: ";
// for (int j : q) cout << j << ' ';
// cout << endl;
// cout << "ans: ";
// for (int j : ans) cout << j << ' ';
// cout << endl;
// cout << "exp: ";
// for (int j : exp) cout << j << ' ';
// cout << endl;
// return 0;
// }
// }
// }
// cout.flush();
// int d = 0;
// d++;
// }
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:103:9: warning: unused variable 'nbQ' [-Wunused-variable]
103 | int nbQ = size(queryL);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23380 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
23364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
660 ms |
33844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
23380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
23380 KB |
Output is correct |
| 2 |
Correct |
11 ms |
23380 KB |
Output is correct |
| 3 |
Correct |
697 ms |
30928 KB |
Output is correct |
| 4 |
Correct |
183 ms |
30324 KB |
Output is correct |
| 5 |
Correct |
1283 ms |
37276 KB |
Output is correct |
| 6 |
Correct |
1403 ms |
38032 KB |
Output is correct |
| 7 |
Correct |
1345 ms |
38704 KB |
Output is correct |
| 8 |
Correct |
1320 ms |
37240 KB |
Output is correct |
| 9 |
Correct |
867 ms |
38744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23380 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
23364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
