| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 702396 | 2023-02-23T22:36:45 Z | thimote75 | Growing Trees (BOI11_grow) | C++14 | 464 ms | 9104 KB |
#include <bits/stdc++.h>
using namespace std;
#define num long long
struct SGD {
num sum = 0;
num size = 1;
num __l_value = 0;
};
struct SegTree {
vector<SGD> tree;
int size, start, height;
SegTree (int ps) {
size = ps;
height = ceil(log2(size));
start = 1 << height;
tree.resize(start << 1);
for (int h = height - 1; h >= 0; h --) {
int s = 1 << h;
for (int i = 0; i < s; i ++)
tree[i + s].size = 2 * tree[(i + s) * 2].size;
}
}
void _update (int index) {
if (index == 0) return ;
if (index >= start) {
_update(index >> 1);
tree[index].sum += tree[index].__l_value * tree[index].size;
tree[index].__l_value = 0;
return ;
}
_update(index >> 1);
int n0 = index << 1;
int n1 = n0 + 1;
tree[n0].__l_value += tree[index].__l_value;
tree[n1].__l_value += tree[index].__l_value;
tree[index].sum += tree[index].__l_value * tree[index].size;
tree[index].__l_value = 0;
}
num _value (int index) {
index += start;
_update(index);
return tree[index].sum;
}
void _modify (int index, int delta) {
_update(index);
tree[index].__l_value += delta;
}
void modify (int left, int right, int delta) {
left += start;
right += start;
while (left < right) {
if ((left & 1) == 1) _modify(left, delta);
if ((right & 1) == 0) _modify(right, delta);
left = (left + 1) >> 1;
right = (right - 1) >> 1;
}
if (left == right) _modify(left, delta);
}
// Find first value such that S[b] > value
int lower_bound (num value) {
int a = -1;
int b = size;
while (b - a > 1) {
int c = (a + b) >> 1;
if (_value(c) > value) b = c;
else a = c;
}
return b;
}
int upper_bound (num value) {
return lower_bound(value - 1); // x >= A <=> x > A - 1
}
int count (int min, int max) {
return lower_bound(max) - upper_bound(min);
}
void update_1 (int min_v, int count) {
int start = upper_bound(min_v);
int end = start + count - 1;
if (end >= size) end = size - 1;
if (end + 1 != size && _value(end) == _value(end + 1)) {
int e_partial = end;
end = upper_bound(_value(e_partial));
int c_partial = e_partial - end + 1;
end --;
int s_partial = lower_bound(_value(e_partial));
modify(s_partial - c_partial, s_partial - 1, 1);
}
modify(start, end, 1);
}
void show () {
for (int x = 0; x < size; x ++)
cout << _value(x) << " ";
cout << endl;
}
};
int main () {
int nbNodes, nbQuery;
scanf("%d%d", &nbNodes, &nbQuery);
SegTree tree(nbNodes);
vector <int> val(nbNodes);
for (int idNode = 0; idNode < nbNodes; idNode ++) scanf("%d", &val[idNode]);
sort(val.begin(), val.end());
for (int idNode = 0; idNode < nbNodes; idNode ++)
tree.modify(idNode, idNode, val[idNode]);
for (int idQ = 0; idQ < nbQuery; idQ ++) {
string bf;
cin >> bf;
if (bf[0] == 'F') {
int c, h;
scanf("%d%d", &c, &h);
tree.update_1(h, c);
} else {
int m0, m1;
scanf("%d%d", &m0, &m1);
printf("%d\n", tree.count(m0, m1));
}
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 395 ms | 8332 KB | Output is correct |
| 2 | Correct | 448 ms | 8448 KB | Output is correct |
| 3 | Correct | 187 ms | 8480 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 ms | 340 KB | Output is correct |
| 2 | Correct | 10 ms | 440 KB | Output is correct |
| 3 | Correct | 10 ms | 440 KB | Output is correct |
| 4 | Correct | 7 ms | 340 KB | Output is correct |
| 5 | Correct | 238 ms | 1776 KB | Output is correct |
| 6 | Correct | 322 ms | 2000 KB | Output is correct |
| 7 | Correct | 15 ms | 724 KB | Output is correct |
| 8 | Correct | 239 ms | 1452 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 316 ms | 1976 KB | Output is correct |
| 2 | Correct | 285 ms | 2084 KB | Output is correct |
| 3 | Correct | 4 ms | 724 KB | Output is correct |
| 4 | Correct | 267 ms | 1636 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 320 ms | 2228 KB | Output is correct |
| 2 | Correct | 315 ms | 1996 KB | Output is correct |
| 3 | Correct | 20 ms | 852 KB | Output is correct |
| 4 | Correct | 289 ms | 2012 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 319 ms | 4784 KB | Output is correct |
| 2 | Correct | 428 ms | 8276 KB | Output is correct |
| 3 | Correct | 73 ms | 2296 KB | Output is correct |
| 4 | Correct | 174 ms | 8120 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 386 ms | 7956 KB | Output is correct |
| 2 | Correct | 450 ms | 8180 KB | Output is correct |
| 3 | Correct | 205 ms | 8376 KB | Output is correct |
| 4 | Correct | 75 ms | 2248 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 372 ms | 7936 KB | Output is correct |
| 2 | Correct | 362 ms | 8108 KB | Output is correct |
| 3 | Correct | 189 ms | 8476 KB | Output is correct |
| 4 | Correct | 80 ms | 2276 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 379 ms | 8456 KB | Output is correct |
| 2 | Correct | 430 ms | 8284 KB | Output is correct |
| 3 | Correct | 69 ms | 7484 KB | Output is correct |
| 4 | Correct | 438 ms | 7880 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 452 ms | 8440 KB | Output is correct |
| 2 | Correct | 367 ms | 8492 KB | Output is correct |
| 3 | Correct | 464 ms | 8628 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 460 ms | 9104 KB | Output is correct |