이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIM 2000010
using namespace std;
vector <int> L[DIM];
deque <int> d;
int low[DIM],v[DIM];
int n,i,j,ans,D,t;
struct segment_tree{
int maxi,poz,lazy;
} aint[DIM*4];
void update_lazy (int nod, int st, int dr){
if (!aint[nod].lazy)
return;
if (st != dr){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[fiu_st].maxi += aint[nod].lazy;
aint[fiu_st].lazy += aint[nod].lazy;
aint[fiu_dr].maxi += aint[nod].lazy;
aint[fiu_dr].lazy += aint[nod].lazy;
}
aint[nod].lazy = 0;
}
void update (int nod, int st, int dr, int x, int y, int val){
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
aint[nod].maxi += val;
aint[nod].lazy += val;
update_lazy (nod,st,dr);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update (nod<<1,st,mid,x,y,val);
if (y > mid)
update ((nod<<1)|1,mid+1,dr,x,y,val);
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
update_lazy (fiu_st,st,mid);
update_lazy (fiu_dr,mid+1,dr);
if (aint[fiu_st].maxi > aint[fiu_dr].maxi)
aint[nod].maxi = aint[fiu_st].maxi, aint[nod].poz = aint[fiu_st].poz;
else aint[nod].maxi = aint[fiu_dr].maxi, aint[nod].poz = aint[fiu_dr].poz;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>D>>t;
for (i=1;i<=n;i++)
cin>>v[i];
for (i=1;i<=n;i++){
while (!d.empty() && v[d.back()] + i - d.back() - t > 0)
d.pop_back();
if (v[i] <= t){
low[i] = -1;
ans++;
continue;
}
if (d.empty())
low[i] = -1;
else {
ans++;
low[i] = d.back();
}
/// trb sa mai scot din stiva in caz ca o pozitie si ar pierde influenta pt ca
/// vine alta care incepe un interval nou
if (v[i] < t){
while (!d.empty() && v[d.back()] - d.back() >= v[i] - i)
d.pop_back();
d.push_back(i);
}
}
for (i=1;i<=n;i++)
if (low[i] != -1 && low[i] <= i-1){
update (1,1,n,low[i],i-1,1);
L[low[i]].push_back(i-1);
}
for (i=1;i<=n;i++)
sort (L[i].begin(),L[i].end());
for (int pas=1;pas<=D;pas++){
int poz = aint[1].poz;
ans -= aint[1].maxi;
for (i=1;i<=poz;i++)
while (L[i].size() && L[i].back() >= poz){
update (1,1,n,i,L[i].back(),-1);
L[i].pop_back();
}
}
cout<<ans;
return 0;
}
# | 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... |