| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 786569 |
2023-07-18T09:21:34 Z |
반딧불(#10026) |
Weirdtree (RMI21_weirdtree) |
C++17 |
|
1145 ms |
524288 KB |
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
map<ll, int> mp[1<<20];
map<ll, int> loc[1<<20];
ll sum[1<<20];
ll lazy[1<<20];
void merge(int i){
sum[i] = sum[i*2] + sum[i*2+1];
}
void init(int i, int l, int r, ll *A){
lazy[i] = INT_MAX;
for(int x=l; x<=r; x++){
if(!mp[i][A[x]]) loc[i][A[x]] = l;
mp[i][A[x]]++;
sum[i] += A[x];
}
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
merge(i);
}
void propagate(int i, int l, int r){
if(lazy[i] == INT_MAX) return;
while(!mp[i].empty() && mp[i].rbegin()->first > lazy[i]){
ll a = mp[i].rbegin()->first; int b = mp[i].rbegin()->second;
mp[i].erase(a);
if(mp[i].empty() || mp[i].rbegin()->first < lazy[i]){ /// �̰Źۿ� ���� ���
sum[i] -= (a-lazy[i]) * b;
loc[i][lazy[i]] = loc[i].rbegin()->second; loc[i].erase(a);
mp[i][lazy[i]] += b;
}
else if(mp[i].rbegin()->first == lazy[i]){ /// �� �°� ��ġ�� ���
sum[i] -= (a-lazy[i]) * b;
loc[i][lazy[i]] = min(loc[i][lazy[i]], loc[i].rbegin()->second); loc[i].erase(a);
mp[i][lazy[i]] += b;
}
else{ /// �� ���� ��ħ
ll c = prev(loc[i].rbegin())->first;
sum[i] = (a-c) * b;
loc[i][c] = min(loc[i][c], loc[i].rbegin()->second); loc[i].erase(a);
mp[i][c] += b;
}
}
if(l!=r){
lazy[i*2] = min(lazy[i*2], lazy[i]);
lazy[i*2+1] = min(lazy[i*2+1], lazy[i]);
}
lazy[i] = INT_MAX;
}
ll update(int i, int l, int r, int s, int e, ll v){ /// v �̻��� ���� v��
propagate(i, l, r);
if(r<s || e<l) return 0;
if(s<=l && r<=e){
int tmp = mp[i].rbegin()->second;
lazy[i] = v;
propagate(i, l, r);
return tmp;
}
int m = (l+r)>>1;
int ret = 0;
ret += update(i*2, l, m, s, e, v);
ret += update(i*2+1, m+1, r, s, e, v);
merge(i);
ll prv = mp[i].rbegin()->first;
mp[i][prv] -= ret, mp[i][v] += ret;
loc[i][prv] = (loc[i*2].find(prv) == loc[i*2].end() ? INT_MAX : loc[i*2][prv],
loc[i*2+1].find(prv) == loc[i*2+1].end() ? INT_MAX : loc[i*2+1][prv]);
loc[i][v] = (loc[i*2].find(v) == loc[i*2].end() ? INT_MAX : loc[i*2][v],
loc[i*2+1].find(v) == loc[i*2+1].end() ? INT_MAX : loc[i*2+1][v]);
return ret;
}
ll updateK(int i, int l, int r, int s, int e, ll v, int k){ /// v �̻��� ���� v��
propagate(i, l, r);
if(r<s || e<l) return 0;
int tmp = (mp[i].find(v+1) == mp[i].end()) ? 0 : mp[i][v+1];
if(s<=l && r<=e && tmp <= k){
lazy[i] = v;
propagate(i, l, r);
return tmp;
}
int m = (l+r)>>1;
propagate(i*2, l, m);
tmp = (mp[i*2].find(v+1) == mp[i*2].end()) ? 0 : mp[i*2][v+1];
ll ret = 0;
ret += updateK(i*2, l, m, s, e, v, k);
if(tmp<k) ret += updateK(i*2+1, m+1, r, s, e, v, k-tmp);
else propagate(i*2+1, m+1, r);
merge(i);
ll prv = mp[i].rbegin()->first;
mp[i][prv] -= ret, mp[i][v] += ret;
loc[i][prv] = (loc[i*2].find(prv) == loc[i*2].end() ? INT_MAX : loc[i*2][prv],
loc[i*2+1].find(prv) == loc[i*2+1].end() ? INT_MAX : loc[i*2+1][prv]);
loc[i][v] = (loc[i*2].find(v) == loc[i*2].end() ? INT_MAX : loc[i*2][v],
loc[i*2+1].find(v) == loc[i*2+1].end() ? INT_MAX : loc[i*2+1][v]);
return ret;
}
void updateSingle(int i, int l, int r, int x, ll prv, ll v){
propagate(i, l, r);
if(l==r){
mp[i].clear(), loc[i].clear();
mp[i][v] = 1, loc[i][v] = l;
sum[i] = v;
return;
}
int m = (l+r)>>1;
if(x<=m) updateSingle(i*2, l, m, x, prv, v), propagate(i*2+1, m+1, r);
else updateSingle(i*2+1, m+1, r, x, prv, v), propagate(i*2, l, m);
sum[i] += v-prv;
mp[i][prv]--;
if(!mp[i][prv]) mp[i].erase(prv), loc[i].erase(prv);
else loc[i][prv] = min(loc[i*2].find(prv) == loc[i*2].end() ? INT_MAX : loc[i*2][prv],
loc[i*2+1].find(prv) == loc[i*2+1].end() ? INT_MAX : loc[i*2+1][prv]);
}
ll querySum(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return 0;
if(s<=l && r<=e) return sum[i];
int m = (l+r)>>1;
return querySum(i*2, l, m, s, e) + querySum(i*2+1, m+1, r, s, e);
}
pair<ll, ll> query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return make_pair(-1, 0);
if(s<=l && r<=e) return *mp[i].rbegin();
int m = (l+r)>>1;
pair<ll, ll> a = query(i*2, l, m, s, e), b = query(i*2+1, m+1, r, s, e);
return make_pair(max(a.first, b.first), (a.first>=b.first ? a.second : 0) + (b.first>=a.first ? b.second : 0));
}
ll smaller(int i, int l, int r, int s, int e, ll v){
propagate(i, l, r);
if(r<s || e<l) return 0;
if(s<=l && r<=e){
if(!mp[i].empty() && mp[i].rbegin()->first < v) return mp[i].rbegin()->first;
else if((int)mp[i].size() >= 2 && mp[i].rbegin()->first == v) return prev(prev(mp[i].end()))->first;
else return 0;
}
int m = (l+r)>>1;
return max(smaller(i*2, l, m, s, e, v), smaller(i*2+1, m+1, r, s, e, v));
}
} tree;
int n, q;
ll arr[300002];
void initialise(int N, int Q, int h[]){
n = N, q = Q;
for(int i=1; i<=n; i++) arr[i] = h[i];
tree.init(1, 1, n, arr);
}
void cut(int l, int r, int k){
while(true){
pair<ll, ll> p = tree.query(1, 1, n, l, r);
ll a = p.first, b = p.second;
if(!a) break;
ll small = tree.smaller(1, 1, n, l, r, a);
if(ll(b)*(a-small) <= k){
k -= ll(b) * (a-small);
tree.update(1, 1, n, l, r, small);
}
else{
ll goal = a-k/b;
if(a != goal) tree.update(1, 1, n, l, r, goal);
if(k%b) tree.updateK(1, 1, n, l, r, goal-1, k%b);
break;
}
}
}
void magic(int i, int x){
tree.updateSingle(1, 1, n, i, tree.querySum(1, 1, n, i, i), x);
}
ll inspect(int l, int r){
return tree.querySum(1, 1, n, l, r);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
116 ms |
203660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
116 ms |
203660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
146 ms |
207452 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
146 ms |
207452 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1145 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
116 ms |
203660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
116 ms |
203660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
