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 ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 300010
#define INF 2000000010
using namespace std;
int N, K, a[MAXN];
int bit[MAXN];
pair<ll, int> seg[4*MAXN];
ll lazy[4*MAXN];
void upd(int x)
{
while (x<MAXN)
{
bit[x]++;
x+=x&(-x);
}
}
int sum(int x)
{
int ret=0;
while (x)
{
ret+=bit[x];
x-=x&(-x);
}
return ret;
}
void relax(int node, int l, int r)
{
seg[node].xx+=lazy[node];
if (l!=r)
{
lazy[2*node]+=lazy[node];
lazy[2*node+1]+=lazy[node];
}
lazy[node]=0;
}
void build(int node, int l, int r)
{
if (l==r) { seg[node]={a[l], l}; return; }
int mid=l+(r-l)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
seg[node]=max(seg[2*node], seg[2*node+1]);
}
void update(int node, int l, int r, int levo, int desno, int val) ///[l,r]-gde sam u segmentnom; [levo,desno]-query;
{
relax(node, l, r);
if (levo>r || levo<l) return;
if (levo<=l && desno>=r) { lazy[node]+=val; return; }
int mid=l+(r-l)/2;
update(2*node, l, mid, levo, desno, val);
update(2*node+1, mid+1, r, levo, desno, val);
relax(2*node, l, mid);
relax(2*node+1, mid+1, r);
seg[node]=max(seg[2*node], seg[2*node+1]);
}
pii query(int node, int l, int r, int levo, int desno)
{
relax(node, l, r);
if (levo>r || desno<l) return {-INF, -INF};
if (levo<=l && desno>=r) return seg[node];
int mid=l+(r-l)/2;
return max(query(2*node, l, mid, levo, desno),
query(2*node+1, mid+1, r, levo, desno));
}
void inicjuj(int n, int k, int *D)
{
N = n, K = k;
for (int i = 0; i < n; ++i)
{
a[i+1] = D[i];
if (a[i+1]>=k) { a[i+1]=-INF; upd(i+1); }
}
build(1, 1, n);
}
void podlej(int a, int b)
{
a++; b++;
update(1, 1, N, a, b, 1);
pii maxx=query(1, 1, N, a, b);
while (maxx.xx>=K)
{
upd(maxx.yy);
update(1, 1, N, maxx.yy, maxx.yy, -INF);
maxx=query(1, 1, N, a, b);
}
}
int dojrzale(int a, int b)
{
a++; b++;
return sum(b)-sum(a-1);
//return (t[a] >= K) + (t[b] >= K); /* cos glupiego */
}
# | 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... |