/*
* 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));
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 (i < 0) {
st[0].set(0, upto);
use.set(0, upto, 0);
}
else {
st[1].set(0, upto);
use.set(0, upto, 0);
use.add(0, upto, 1);
}
//
// for (int j = 0; j < n; j++) {
// int res;
// if (use[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 d = 0;
// d++;
//
}
vi ans;
for (pii x : sorted) {
int i = x.s;
int res;
if (use.get(i) == 0) {
res = st[0].get(i);
}
else {
res = st[1].get(i);
res = b[i]-res;
}
assert(0 <= res && res <= x.f);
ans.pb(res);
}
return ans;
}
// signed main() {
// cin.tie(0);
// ios_base::sync_with_stdio(0);
// vi a = distribute_candies({5, 9, 12, 29, 56}, {}, {}, {+7, +6, -12, +4});
// for (int i : a) cout << i << " ";
// 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 |
23340 KB |
Output is correct |
| 2 |
Runtime error |
35 ms |
47360 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
626 ms |
68052 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
23380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
47312 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23340 KB |
Output is correct |
| 2 |
Runtime error |
35 ms |
47360 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
