| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 502136 |
2022-01-05T10:52:24 Z |
benk |
Growing Trees (BOI11_grow) |
C++17 |
|
1000 ms |
6916 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, int 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, int val) {
return right_descend(1, 0, len - 1, l, r, val);
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
sort(all(v));
SegTree st(n);
st.build(v);
while (m--) {
char ch;
cin >> ch;
if (ch == 'F') {
int cap, h;
cin >> cap >> h;
int id1 = st.right_descend(0, n, h);
if (id1 == - 1) continue;
if (id1 + cap >= n) st.rupd(id1, n, 1);
else {
ll curr = st.pquery(id1 + cap).ans;
int id2 = st.right_descend(0, n, curr);
st.rupd(id1, id2 - 1, 1);
int id3 = st.right_descend(0, n, curr + 1);
if (id3 == -1) id3 = n;
id3--;
int left = cap - (id2 - id1);
st.rupd(id3 - left + 1, id3, 1);
}
} else {
int mn, mx;
cin >> mn >> mx;
int id1 = st.right_descend(0, n, mn);
int id2 = st.right_descend(0, n, mx);
if (id1 == -1) cout << "0\n";
else if (id2 == -1) cout << n - id1 << '\n';
else cout << id2 - id1 + 1 << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
cout << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
6216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1068 ms |
904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1084 ms |
920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
4700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
5352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
5708 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
6096 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
6044 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
6916 KB |
Time limit exceeded |
