| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 502188 |
2022-01-05T12:41:12 Z |
benk |
Growing Trees (BOI11_grow) |
C++17 |
|
1000 ms |
7300 KB |
#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 all(x) x.begin(), x.end()
#define pb push_back
#define sz(x) (int)(x.size())
#define ll long long
#define fi first
#define se second
#define lbd lower_bound
#define ubd upper_bound
template <typename T>
using ordered_set = tree<T, null_type,
less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 2e5 + 10;
struct node {
ll ans = 0;
int lazy = 0;
bool islazy = false;
// only used to assign value to 'leaf' nodes in build and pupd
void assign(int val) {
ans = val;
}
// used in build, rquery, pupd, rupd
void merge(const node & l, const node & r) {
ans = l.ans + r.ans;
}
};
struct SegTree {
int32_t len = 0;
node zero;
vector<node> tree;
SegTree (int32_t _len = N) {
len = _len;
tree.resize((len << 2) + 10);
}
// if a node has lazy tag then its info is correct but its children's info
// is old, so pushdown() before going into children
inline void pushdown(int32_t v, int32_t cl, int32_t cr) {
if (!tree[v].islazy) return;
int32_t mid = (cl + cr) >> 1;
apply((v << 1), cl, mid, tree[v].lazy);
apply(((v << 1) | 1), mid + 1, cr, tree[v].lazy);
tree[v].lazy = zero.lazy;
tree[v].islazy = false;
return;
}
// apply() is an auxillary function to apply range update and set lazy tag
inline void apply(int32_t v, int32_t cl, int32_t cr, int val) {
if (cl != cr) {
tree[v].lazy += val; // modify the lazy by val, eg. lazy += val
tree[v].islazy = true;
}
// incorporate the change (=val) in node
tree[v].ans += 1LL * (cr - cl + 1) * val;
return;
}
void build(vector<int32_t> &a, int32_t v, int32_t cl, int32_t cr) {
if (cl == cr) {
tree[v].assign(a[cl]);
return;
}
int32_t mid = (cl + cr) >> 1;
build(a, (v << 1), cl, mid);
build(a, ((v << 1) | 1), mid + 1, cr);
tree[v].merge(tree[(v << 1)], tree[((v << 1) | 1)]);
return;
}
void build(vector<int32_t> &a) {
build(a, 1, 0, len - 1);
return;
}
node pquery(int32_t v, int32_t cl, int32_t cr, int32_t pos) {
if (cl == cr) return tree[v];
pushdown(v, cl, cr);
int32_t mid = (cl + cr) >> 1;
if (pos <= mid) return pquery((v << 1), cl, mid, pos);
return pquery(((v << 1) | 1), mid + 1, cr, pos);
}
node pquery(int32_t pos) {
return pquery(1, 0, len - 1, pos);
}
node rquery(int32_t v, int32_t cl, int32_t cr, int32_t l, int32_t r) {
if (l > cr || r < cl) return zero;
if (l <= cl && cr <= r) return tree[v];
pushdown(v, cl, cr);
int32_t mid = (cl + cr) >> 1;
node a, b, ans;
a = rquery((v << 1), cl, mid, l, r);
b = rquery(((v << 1) | 1), mid + 1, cr, l, r);
ans.merge(a, b);
return ans;
}
node rquery(int32_t l, int32_t r) {
return rquery(1, 0, len - 1, l, r);
}
void pupd(int32_t v, int32_t cl, int32_t cr, int32_t pos, int val) {
if (cl == cr) {
tree[v].assign(val);
return;
}
pushdown(v, cl, cr);
int32_t mid = (cl + cr) >> 1;
if (pos <= mid) {
pupd((v << 1), cl, mid, pos, val);
} else {
pupd(((v << 1) | 1), mid + 1, cr, pos, val);
}
tree[v].merge(tree[(v << 1)], tree[((v << 1) | 1)]);
return;
}
void pupd(int32_t pos, int val) {
pupd(1, 0, len - 1, pos, val);
return;
}
void rupd(int32_t v, int32_t cl, int32_t cr, int32_t l, int32_t r, int val) {
if (l > cr || r < cl) return;
if (l <= cl && cr <= r) {
apply(v, cl, cr, val);
return;
}
pushdown(v, cl, cr);
int32_t mid = (cl + cr) >> 1;
rupd((v << 1), cl, mid, l, r, val);
rupd(((v << 1) | 1), mid + 1, cr, l, r, val);
tree[v].merge(tree[(v << 1)], tree[((v << 1) | 1)]);
return;
}
void rupd(int32_t l, int32_t r, int val) {
rupd(1, 0, len - 1, l, r, val);
}
int right_descend(int32_t v, int32_t cl, int32_t cr, int32_t l, int32_t r, ll val) {
if (cl > r || cr < l) return -1;
if (l <= cl && cr <= r) {
if (tree[v].ans < val) return -1;
}
if (cl == cr) return cl;
pushdown(v, cl, cr);
int32_t mid = (cl + cr) >> 1;
int res = right_descend((v << 1), cl, mid, l, r, val);
if (res != -1) return res;
return right_descend(((v << 1) | 1), mid + 1, cr, l, r, val);
}
int right_descend(int l, int r, ll val) {
return right_descend(1, 0, len - 1, l, r, val);
}
};
void solve() {
int n, m;
scanf("%d%d", &n, &m);
// cin >> n >> m;
vector<int> v(n);
for (int i = 0; i < n; i++) {
// cin >> v[i];
scanf("%d", &v[i]);
}
sort(all(v));
SegTree st(n);
st.build(v);
while (m--) {
char ch;
// cin >> ch;
scanf("\n%c", &ch);
if (ch == 'F') {
int cap, h;
scanf("%d%d", &cap, &h);
// cin >> cap >> h;
int id1 = st.right_descend(0, n - 1, h);
if (id1 == - 1) continue;
if (id1 + cap >= n) st.rupd(id1, n - 1, 1);
else {
ll curr = st.pquery(id1 + cap).ans;
int id2 = st.right_descend(0, n - 1, curr);
if (id1 != id2) st.rupd(id1, id2 - 1, 1);
int id3 = st.right_descend(0, n - 1, curr + 1);
if (id3 == -1) id3 = n;
id3--;
int left = cap - (id2 - id1);
st.rupd(id3 - left + 1, id3, 1);
}
} else {
int mn, mx;
scanf("%d%d", &mn, &mx);
// cin >> mn >> mx;
int id1 = st.right_descend(0, n - 1, mn);
int id2 = st.right_descend(0, n - 1, mx + 1);
if (id1 == -1) printf("0\n");
else if (id2 == -1) printf("%d\n", n - id1);
else printf("%d\n", id2 - id1);
}
}
}
int main() {
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
Compilation message
grow.cpp: In function 'void solve()':
grow.cpp:169:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
grow.cpp:174:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
174 | scanf("%d", &v[i]);
| ~~~~~^~~~~~~~~~~~~
grow.cpp:183:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | scanf("\n%c", &ch);
| ~~~~~^~~~~~~~~~~~~
grow.cpp:186:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
186 | scanf("%d%d", &cap, &h);
| ~~~~~^~~~~~~~~~~~~~~~~~
grow.cpp:203:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
203 | scanf("%d%d", &mn, &mx);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1058 ms |
6484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
428 KB |
Output is correct |
| 2 |
Correct |
42 ms |
456 KB |
Output is correct |
| 3 |
Correct |
28 ms |
432 KB |
Output is correct |
| 4 |
Correct |
25 ms |
424 KB |
Output is correct |
| 5 |
Execution timed out |
1069 ms |
1236 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1061 ms |
1232 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1061 ms |
1056 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1038 ms |
4952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1068 ms |
5580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1083 ms |
5828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
6468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
6212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
7300 KB |
Time limit exceeded |
