| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 333146 |
2020-12-04T19:25:29 Z |
smax |
Growing Trees (BOI11_grow) |
C++17 |
|
125 ms |
9452 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}
struct Node {
int mx, cnt, lazy = 0, l, r;
void leaf(int val) {
mx = val;
cnt = 1;
}
void pull(Node &a, Node &b) {
mx = max(a.mx, b.mx);
cnt = a.cnt + b.cnt;
}
void push(int val) {
lazy += val;
}
void apply() {
mx += lazy;
lazy = 0;
}
};
struct SegmentTree {
int n;
vector<int> a;
vector<Node> st;
SegmentTree(int _n) : n(_n), st(4*n) {
build(1, 0, n-1);
}
SegmentTree(const vector<int> &_a) : n(_a.size()), a(_a), st(4*n) {
build(1, 0, n-1);
}
void build(int p, int l, int r) {
st[p].l = l;
st[p].r = r;
if (l == r) {
st[p].leaf(a[l]);
return;
}
int m = (l + r) / 2;
build(2*p, l, m);
build(2*p+1, m+1, r);
st[p].pull(st[2*p], st[2*p+1]);
}
void push(int p) {
if (st[p].lazy) {
if (st[p].l != st[p].r) {
st[2*p].push(st[p].lazy);
st[2*p+1].push(st[p].lazy);
}
st[p].apply();
}
}
Node query(int p, int i, int j) {
push(p);
if (st[p].l == i && st[p].r == j)
return st[p];
int m = (st[p].l + st[p].r) / 2;
if (j <= m)
return query(2*p, i, j);
else if (i > m)
return query(2*p+1, i, j);
Node ret, ls = query(2*p, i, m), rs = query(2*p+1, m+1, j);
ret.pull(ls, rs);
return ret;
}
int query(int i, int j) {
return query(1, i, j).mx;
}
void update(int p, int i, int j, int val) {
if (st[p].l == i && st[p].r == j) {
st[p].push(val);
push(p);
return;
}
push(p);
int m = (st[p].l + st[p].r) / 2;
if (j <= m) {
update(2*p, i, j, val);
push(2*p+1);
} else if (i > m) {
push(2*p);
update(2*p+1, i, j, val);
} else {
update(2*p, i, m, val);
update(2*p+1, m+1, j, val);
}
st[p].pull(st[2*p], st[2*p+1]);
}
void update(int i, int j, int val) {
if (i > j) return;
update(1, i, j, val);
}
int leftMost(int p, int h) {
if (st[p].l == st[p].r) {
if (st[p].mx < h)
return st[p].l + 1;
return st[p].l;
}
push(2*p);
push(2*p+1);
if (st[2*p].mx >= h)
return leftMost(2*p, h);
return leftMost(2*p+1, h);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i=0; i<n; i++)
cin >> a[i];
sort(a.begin(), a.end());
SegmentTree st(a);
for (int i=0; i<m; i++) {
char t;
cin >> t;
if (t == 'F') {
int c, h;
cin >> c >> h;
int l = st.leftMost(1, h);
if (l + c - 1 < n - 1) {
int finalValue = st.query(l + c - 1, l + c - 1), nextToFinal = st.query(l + c, l + c);
if (finalValue == nextToFinal) {
// to maintain sorted array, instead update separate range
int firstOfFinal = st.leftMost(1, finalValue), firstNotFinal = st.leftMost(1, finalValue + 1);
int sz = l + c - firstOfFinal;
assert(firstOfFinal - l + sz == c);
st.update(l, firstOfFinal - 1, 1);
st.update(firstNotFinal - sz, firstNotFinal - 1, 1);
} else {
st.update(l, min(l + c - 1, n - 1), 1);
}
}
} else {
int mn, mx;
cin >> mn >> mx;
int l = st.leftMost(1, mn), r = st.leftMost(1, mx + 1);
cout << r - l << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
7916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
1260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
1132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
5996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
6892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
7276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
8044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
9452 KB |
Output isn't correct |
