# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
373267 |
2021-03-04T01:11:00 Z |
rk42745417 |
Po (COCI21_po) |
C++17 |
|
171 ms |
3052 KB |
#include <bits/stdc++.h>
using namespace std;
#define EMT ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 2e18;
const double EPS = 1e-9;
const int N = 1e5 + 25;
struct segtree {
int arr[N << 2], tag[N << 2], n;
inline void pull(int p) { arr[p] = min(arr[p << 1], arr[p << 1 | 1]) + tag[p]; }
inline void push(int p) {
arr[p << 1] += tag[p];
tag[p << 1] += tag[p];
arr[p << 1 | 1] += tag[p];
tag[p << 1 | 1] += tag[p];
tag[p] = 0;
}
inline void build(int l, int r, int id, vector<int> &w) {
if(l == r - 1) {
arr[id] = w[l];
return;
}
int m = l + r >> 1;
build(l, m, id << 1, w);
build(m, r, id << 1 | 1, w);
pull(id);
}
inline void init(vector<int> &w) { n = w.size(); build(0, n, 1, w); }
int que(int l, int r, int id, int ql, int qr) {
if(ql <= l && r <= qr)
return arr[id];
if(r <= ql || qr <= l)
return INF;
push(id);
int m = l + r >> 1;
return min(que(l, m, id << 1, ql, qr), que(m, r, id << 1 | 1, ql, qr));
}
inline int que(int l, int r) { return que(0, n, 1, l, r); }
int get(int l, int r, int id, int ql) {
if(r <= ql || arr[id])
return INF;
if(l == r - 1)
return l;
push(id);
int m = l + r >> 1;
int w = get(l, m, id << 1, ql);
if(w == INF)
return get(m, r, id << 1 | 1, ql);
return w;
}
inline int get(int l) { return get(0, n, 1, l); }
void edt(int l, int r, int id, int ql, int qr, int v) {
if(r <= ql || qr <= l)
return;
if(ql <= l && r <= qr) {
arr[id] += v;
tag[id] += v;
return;
}
push(id);
int m = l + r >> 1;
edt(l, m, id << 1, ql, qr, v);
edt(m, r, id << 1 | 1, ql, qr, v);
pull(id);
}
inline void edt(int l, int r, int v) { edt(0, n, 1, l, r, v); }
} tree;
signed main() { EMT
int n;
cin >> n;
vector<int> arr(n + 1);
for(int i = 0; i < n; i++)
cin >> arr[i];
tree.init(arr);
int it = 0, ans = 0;
while(it < n) {
if(!tree.que(it, it + 1)) {
it++;
continue;
}
int w = tree.get(it);
int m = tree.que(it, w);
tree.edt(it, w, -m);
ans++;
}
cout << ans << '\n';
}
Compilation message
Main.cpp: In member function 'void segtree::build(int, int, int, std::vector<int>&)':
Main.cpp:31:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | int m = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'int segtree::que(int, int, int, int, int)':
Main.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int m = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'int segtree::get(int, int, int, int)':
Main.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int m = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'void segtree::edt(int, int, int, int, int, int)':
Main.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int m = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
55 ms |
1772 KB |
Output is correct |
5 |
Correct |
88 ms |
2796 KB |
Output is correct |
6 |
Correct |
114 ms |
2924 KB |
Output is correct |
7 |
Correct |
171 ms |
3052 KB |
Output is correct |