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>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define maxn 300005
#define pii pair<int,int>
#define pb push_back
#define xx first
#define yy second
#define MAXN 3005
using namespace std;
int N, K;
int seg[4 * maxn];
int idx[4 * maxn];
int lejzi[4 * maxn];
int niz[maxn];
void propagate(int node, int l, int r){
if(lejzi[node]){
if(l != r){
lejzi[node * 2] += lejzi[node];
lejzi[node * 2 + 1] += lejzi[node];
}
seg[node] += lejzi[node];
lejzi[node] = 0;
}
}
void init(int node, int l, int r){
if(l == r){
seg[node] = niz[l];
idx[node] = l;
return;
}
int mid = (l + r) / 2;
init(node * 2, l, mid);
init(node * 2 + 1, mid + 1, r);
seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
if(seg[node * 2] < seg[node * 2 + 1])idx[node] = idx[node * 2];
else idx[node] = idx[node * 2 + 1];
}
void apdejt(int node, int l, int r, int levo, int desno, int val){
propagate(node, l, r);
if(r < levo || l > desno)return;
if(l >= levo && r <= desno){
lejzi[node] += val;
propagate(node, l, r);
return;
}
int mid = (l + r) / 2;
apdejt(node * 2, l, mid, levo, desno, val);
apdejt(node * 2 + 1, mid + 1, r, levo, desno, val);
seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
if(seg[node * 2] < seg[node * 2 + 1])idx[node] = idx[node * 2];
else idx[node] = idx[node * 2 + 1];
}
pii query(int node, int l, int r, int levo, int desno){
if(l >= levo && r <= desno)return {seg[node], idx[node]};
if(r < levo || l > desno)return {-1e9, 1};
int mid = (l + r) / 2;
return max(query(node * 2, l, mid, levo, desno), query(node * 2 + 1, mid + 1, r, levo, desno));
}
int bit[maxn];
void apdejtbit(int x){
while(x <= N){
bit[x]++;
x += (x&-x);
}
}
int kveribit(int x){
int res = 0;
while(x > 0){
res += bit[x];
x -= (x&-x);
}
return res;
}
void namesti(int le, int ri){
while(1){
pii sta = query(1,1,N,le,ri);
if(sta.xx < 0)break;
apdejtbit(sta.yy);
apdejt(1,1,N,sta.yy,sta.yy,-1e9-sta.xx);
}
}
void inicjuj(int n, int k, int *D)
{
N = n, K = k;
for(int i=0; i<n; i++){
niz[i + 1] = D[i] - k;
}
init(1,1,n);
}
void podlej(int a, int b)
{
a++;
b++;
apdejt(1,1,b,a,b,1);
namesti(a,b);
}
int dojrzale(int a, int b)
{
a++;
b++;
return kveribit(a) - kveribit(b - 1);
}
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |