This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int o = 262144, inf = 1e8;
struct Idxtree{
int a[o+o];
void init(int n, int *r){
memset(a,0,sizeof(a));
for(int i = 0; i < n; i++){
a[o + i] = r[i];
}
for(int x = o; x > 1; x >>= 1){
for(int y = x; y < x + x; y += 2){
a[y >> 1] = max(a[y], a[y^1]);
}
}
}
int RMQ(int s, int e){
s += o, e += o;
int ret = max(a[s], a[e]);
while(s <= e){
ret = max({ret, a[s], a[e]});
(++s) >>= 1;
(--e) >>= 1;
}
return ret;
}
void upd(int i, int v){
i += o;
a[i] = v;
while(i > 1){
a[i >> 1] = max(a[i], a[i^1]);
i >>= 1;
}
}
} I;
int d[o];
int n, a, q;
set<pii,greater<pii>> S;
void init(){
cin >> n >> a;
d[0] = d[n+1] = inf;
for(int i = 1; i <= n; i++){
cin >> d[i];
}
n += 1;
cin >> q;
I.init(n+1, d);
for(int i = 1; i < n; i++){
S.emplace(d[i],i);
}
while(S.size() > 10) S.erase(*S.rbegin());
}
void enhance(int k, int e){
int nv = S.begin() -> first + 1;
pii t[10];
for(int i = 0; i < e - 1; i++){
t[i] = *S.begin();
S.erase(t[i]);
nv = t[i].first;
}
for(int i = 0; i < e - 1; i++){
S.emplace(d[t[i].second] = t[i].first + 1, t[i].second);
I.upd(t[i].second, d[t[i].second]);
}
S.erase({d[k], k});
S.emplace(d[k] = nv, k);
I.upd(k, d[k]);
while(S.size() > 10) S.erase(*S.rbegin());
}
int bs_min(int X){
if(I.a[o + a - 1] > X) return a;
int lo = 0, mi, hi = a - 1;
while(lo < hi){
mi = (lo + hi) >> 1;
if(I.RMQ(mi, a-1) > X) lo = mi + 1;
else hi = mi;
}
return hi;
}
int bs_MAX(int X){
if(I.a[o + a + 1] > X) return a;
int lo = a + 1, mi, hi = n;
while(lo < hi){
mi = (lo + hi + 1) >> 1;
if(I.RMQ(a+1, mi) > X) hi = mi - 1;
else lo = mi;
}
return lo;
}
int numCake(int l){
if(l > a){
return l - bs_min(I.RMQ(a+1, l));
}else if(l < a){
return bs_MAX(I.RMQ(l, a-1)) - l;
}else{
return 0;
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
init();
char c;
for(int u, v, i = 0; i < q; i++){
cin >> c;
if(c == 'E'){
cin >> u >> v;
enhance(u, v);
}else{
cin >> u;
cout << numCake(u) << '\n';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |