| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1068315 |
2024-08-21T09:14:07 Z |
정민찬(#11128) |
Weirdtree (RMI21_weirdtree) |
C++17 |
|
2000 ms |
416896 KB |
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 2e18;
struct SegmentTree{
vector<map<ll,ll,greater<ll>>> tree;
vector<ll> sum;
vector<ll> lazy;
void init(ll n) {
ll sz = 1 << __lg(n-1) + 2;
tree.resize(sz);
lazy.assign(sz, inf);
sum.assign(sz, 0);
}
vector<pll> propagate(ll node, ll s, ll e) {
if (lazy[node] == inf) return {};
vector<pll> ret;
while (!tree[node].empty()) {
if (tree[node].begin()->first <= lazy[node]) break;
ret.push_back(*tree[node].begin());
sum[node] -= (tree[node].begin()->first - lazy[node]) * tree[node].begin()->second;
tree[node][lazy[node]] += tree[node].begin()->second;
tree[node].erase(tree[node].begin());
}
if (s != e) {
lazy[node*2] = min(lazy[node], lazy[node*2]);
lazy[node*2+1] = min(lazy[node], lazy[node*2+1]);
}
lazy[node] = inf;
return ret;
}
void Push(ll node, ll s, ll e, ll tar, ll val) {
propagate(node, s, e);
if (s > tar || tar > e) return;
tree[node][val] ++;
sum[node] += val;
if (s == e) return;
ll mid = s + e >> 1;
Push(node*2, s, mid, tar, val);
Push(node*2+1, mid+1, e, tar, val);
}
void Ers(ll node, ll s, ll e, ll tar, ll val) {
propagate(node, s, e);
if (s > tar || tar > e) return;
tree[node][val] --;
if (tree[node][val] == 0) tree[node].erase(val);
sum[node] -= val;
if (s == e) return;
ll mid = s + e >> 1;
Ers(node*2, s, mid, tar, val);
Ers(node*2+1, mid+1, e, tar, val);
}
vector<pll> update(ll node, ll s, ll e, ll l, ll r, ll v) {
propagate(node, s, e);
if (l > e || s > r) return {};
if (l <= s && e <= r) {
lazy[node] = v;
return propagate(node, s, e);
}
ll mid = s + e >> 1;
vector<pll> t1 = update(node*2, s, mid, l, r, v);
vector<pll> t2 = update(node*2+1, mid+1, e, l, r, v);
vector<pll> ret;
ret.reserve(t1.size() + t2.size());
for (auto &x : t1) ret.push_back(x);
for (auto &x : t2) ret.push_back(x);
for (auto &[h, cnt] : ret) {
sum[node] -= (h - v) * cnt;
tree[node][v] += cnt;
tree[node][h] -= cnt;
if (tree[node][h] == 0) tree[node].erase(h);
}
return ret;
}
pll getMax(ll node, ll s, ll e, ll l, ll r) {
propagate(node, s, e);
if (l > e || s > r) return {0, 0};
if (l <= s && e <= r) {
return {tree[node].begin()->first, tree[node].begin()->second};
}
ll mid = s + e >> 1;
pll t1 = getMax(node*2, s, mid, l, r);
pll t2 = getMax(node*2+1, mid+1, e, l, r);
if (t1.first > t2.first) return t1;
if (t1.first < t2.first) return t2;
return {t1.first, t1.second + t2.second};
}
ll getSecond(ll node, ll s, ll e, ll l, ll r, ll k) {
propagate(node, s, e);
if (l > e || s > r) return 0;
if (l <= s && e <= r) {
if (tree[node].begin()->first != k) return tree[node].begin()->first;
if (tree[node].size() == 1) return 0;
return next(tree[node].begin())->first;
}
ll mid = s + e >> 1;
return max(getSecond(node*2, s, mid, l, r, k), getSecond(node*2+1, mid+1, e, l, r, k));
}
ll getSum(ll node, ll s, ll e, ll l, ll r) {
propagate(node, s, e);
if (l > e || s > r) return 0;
if (l <= s && e <= r) return sum[node];
ll mid = s + e >> 1;
return getSum(node*2, s, mid, l, r) + getSum(node*2+1, mid+1, e, l, r);
}
pll findLeft(ll node, ll s, ll e, ll l, ll r, ll mx, ll k) {
propagate(node, s, e);
if (l > e || s > r) return {-1, 0};
if (tree[node].empty() || tree[node].begin()->first < mx) return {-1, 0};
if (tree[node].begin()->first == mx && tree[node].begin()->second < k) return {-1, tree[node].begin()->second};
if (s == e) return {s, 0};
ll mid = s + e >> 1;
pll t1 = findLeft(node*2, s, mid, l, r, mx, k);
if (t1.first == -1) {
pll t2 = findLeft(node*2+1, mid+1, e, l, r, mx, k - t1.second);
return {t2.first, t1.second + t2.second};
}
return t1;
}
};
SegmentTree seg;
ll n;
void initialise(int N, int Q, int h[]) {
n = N;
seg.init(N);
for (ll i=1; i<=N; i++) {
seg.Push(1, 1, N, i, h[i]);
}
}
void cut(int l, int r, int _k) {
ll k = _k;
while (true) {
pll ret = seg.getMax(1, 1, n, l, r);
ll mx = ret.first, cnt = ret.second;
ll sec = seg.getSecond(1, 1, n, l, r, mx);
if (mx == 0) break;
if ((mx - sec) * cnt <= k) {
seg.update(1, 1, n, l, r, sec);
k -= (mx - sec) * cnt;
continue;
}
ll diff = k / cnt;
seg.update(1, 1, n, l, r, mx - diff);
k %= cnt;
if (k == 0) break;
ll idx = seg.findLeft(1, 1, n, l, r, mx - diff, k).first;
//if (idx == -1) break;
assert(idx != -1);
seg.update(1, 1, n, l, idx, mx - diff - 1);
break;
}
}
void magic(int i, int x) {
ll cur = seg.getSum(1, 1, n, i, i);
seg.Ers(1, 1, n, i, cur);
seg.Push(1, 1, n, i, x);
}
long long int inspect(int l, int r) {
return seg.getSum(1, 1, n, l, r);
}
/*
int main() {
int N, Q;
cin >> N >> Q;
int h[N + 1];
for (int i = 1; i <= N; ++i) cin >> h[i];
initialise(N, Q, h);
for (int i = 1; i <= Q; ++i) {
int t;
cin >> t;
if (t == 1) {
int l, r, k;
cin >> l >> r >> k;
cut(l, r, k);
} else if (t == 2) {
int i, x;
cin >> i >> x;
magic(i, x);
} else {
int l, r;
cin >> l >> r;
cout << inspect(l, r) << '\n';
}
}
return 0;
}*/
Compilation message
weirdtree.cpp: In member function 'void SegmentTree::init(ll)':
weirdtree.cpp:15:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
15 | ll sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
weirdtree.cpp: In member function 'void SegmentTree::Push(ll, ll, ll, ll, ll)':
weirdtree.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | ll mid = s + e >> 1;
| ~~^~~
weirdtree.cpp: In member function 'void SegmentTree::Ers(ll, ll, ll, ll, ll)':
weirdtree.cpp:54:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | ll mid = s + e >> 1;
| ~~^~~
weirdtree.cpp: In member function 'std::vector<std::pair<long long int, long long int> > SegmentTree::update(ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | ll mid = s + e >> 1;
| ~~^~~
weirdtree.cpp: In member function 'pll SegmentTree::getMax(ll, ll, ll, ll, ll)':
weirdtree.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | ll mid = s + e >> 1;
| ~~^~~
weirdtree.cpp: In member function 'll SegmentTree::getSecond(ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:101:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
101 | ll mid = s + e >> 1;
| ~~^~~
weirdtree.cpp: In member function 'll SegmentTree::getSum(ll, ll, ll, ll, ll)':
weirdtree.cpp:108:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
108 | ll mid = s + e >> 1;
| ~~^~~
weirdtree.cpp: In member function 'pll SegmentTree::findLeft(ll, ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:117:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
117 | ll mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1039 ms |
100268 KB |
Output is correct |
| 4 |
Correct |
1068 ms |
98388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
14 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
14 ms |
1116 KB |
Output is correct |
| 3 |
Execution timed out |
2036 ms |
416896 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2067 ms |
402516 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1039 ms |
100268 KB |
Output is correct |
| 4 |
Correct |
1068 ms |
98388 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1112 KB |
Output is correct |
| 6 |
Correct |
14 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
1048 ms |
100904 KB |
Output is correct |
| 8 |
Correct |
1018 ms |
98388 KB |
Output is correct |
| 9 |
Correct |
1028 ms |
97964 KB |
Output is correct |
| 10 |
Correct |
1183 ms |
103636 KB |
Output is correct |
| 11 |
Correct |
1071 ms |
105560 KB |
Output is correct |
| 12 |
Correct |
53 ms |
28432 KB |
Output is correct |
| 13 |
Correct |
148 ms |
30556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1039 ms |
100268 KB |
Output is correct |
| 4 |
Correct |
1068 ms |
98388 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1112 KB |
Output is correct |
| 6 |
Correct |
14 ms |
1116 KB |
Output is correct |
| 7 |
Execution timed out |
2036 ms |
416896 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
