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;
int N, K, t[10];
int n;
struct segment{
int mx, idx, lazy;
} seg[2000005];
int bit[300005];
int niz[300005];
const int INF = 1000000000;
int getbit(int x){
int res = 0;
while(x){
res += bit[x];
x -= x & -x;
}
return res;
}
void addbit(int x){
while(x <= 300000){
bit[x]++;
x += x & -x;
}
}
void propagate(int node, int l, int r){
seg[node].mx += seg[node].lazy;
if(l == r){
seg[node].lazy = 0;
return;
}
seg[node*2].lazy += seg[node].lazy;
seg[node*2+1].lazy += seg[node].lazy;
seg[node].lazy = 0;
}
void init(int node, int l, int r){
if(l == r){
seg[node].mx = niz[l];
seg[node].idx = l;
return;
}
int mid = (l+r)/2;
init(node*2, l, mid);
init(node*2+1, mid+1, r);
seg[node].mx = max(seg[node*2].mx, seg[node*2+1].mx);
seg[node].idx = seg[node*2+1].idx;
if(seg[node].mx == seg[node*2].mx) seg[node].idx = seg[node*2].idx;
}
void upd(int node, int l, int r, int tl, int tr, int val){
propagate(node, l, r);
if(tl > r || l > tr) return;
if(tl <= l && r <= tr){
seg[node].lazy += val;
propagate(node, l, r);
return;
}
int mid = (l+r)/2;
upd(node*2, l, mid, tl, tr, val);
upd(node*2+1, mid+1, r, tl, tr, val);
seg[node].mx = max(seg[node*2].mx, seg[node*2+1].mx);
seg[node].idx = seg[node*2+1].idx;
if(seg[node].mx == seg[node*2].mx) seg[node].idx = seg[node*2].idx;
}
void inicjuj(int n, int k, int *D)
{
N = n, K = k;
for(int i=1; i<=N; i++) niz[i] = D[i-1];
init(1, 1, N);
while(seg[1].mx >= K){
upd(1, 1, n, seg[1].idx, seg[1].idx, -INF);
addbit(seg[1].idx);
}
}
void podlej(int a, int b)
{
a++;
b++;
upd(1, 1, N, a, b, 1);
while(seg[1].mx >= K){
upd(1, 1, n, seg[1].idx, seg[1].idx, -INF);
addbit(seg[1].idx);
}
}
int dojrzale(int a, int b)
{
a++;
b++;
return getbit(b) - getbit(a-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... |