이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N = 2e6+50, mod = 998244353, K = 31;
int n,d,T;
int cnt = 0;
int L[N],R[N],B[N],A[N],gar[N],shig[N];
bool fix[N];
pair<int,int>mx[N*4];
int toadd[N*4];
inline void upd(int node,int tl,int tr,int l,int r,int val){
if(tl > r || l > tr) return ;
if(tl == tr){
mx[node].ff += val;
mx[node].ss = tl;
return ;
}
if(l <= tl && tr <= r){
mx[node].ff += val;
toadd[node] += val;
return ;
}
int mid = (tl+tr)/2;
int left = node*2;
int right = left+1;
if(toadd[node]){
toadd[left] += toadd[node];
toadd[right] += toadd[node];
mx[left].ff += toadd[node];
mx[right].ff += toadd[node];
toadd[node] = 0;
}
upd(left,tl,mid,l,r,val);
upd(right,mid+1,tr,l,r,val);
mx[node] = max(mx[left],mx[right]);
}
inline void upd1(int node,int tl,int tr,int l,int r){
if(tl > r || l > tr) return ;
if(tl == tr){
mx[node].ff = L[tl+1] - L[tl];
mx[node].ss = tl;
return ;
}
int mid = (tl+tr)/2;
int left = node*2;
int right = left+1;
if(toadd[node]){
toadd[left] += toadd[node];
toadd[right] += toadd[node];
mx[left].ff += toadd[node];
mx[right].ff += toadd[node];
toadd[node] = 0;
}
upd1(left,tl,mid,l,r);
upd1(right,mid+1,tr,l,r);
mx[node] = max(mx[left],mx[right]);
}
inline void upd2(int node,int tl,int tr,int pos){
if(tl == tr){
mx[node] = {0,tl};
return ;
}
int mid = (tl+tr)/2;
int left = node*2;
int right = left+1;
if(toadd[node]){
toadd[left] += toadd[node];
toadd[right] += toadd[node];
mx[left].ff += toadd[node];
mx[right].ff += toadd[node];
toadd[node] = 0;
}
if(pos <= mid){
upd2(left,tl,mid,pos);
} else {
upd2(right,mid+1,tr,pos);
}
mx[node] = max(mx[left],mx[right]);
}
inline void test_case(){
cin >> n >> d >> T;
for(int i = 1; i <= n; i++){
cin >> A[i];
if(A[i] <= T){
cnt++;
L[cnt] = i;
R[cnt] = min(n,T-A[i]+i);
B[i]++;
B[R[cnt]+1]--;
if(L[cnt] <= R[cnt-1] && R[cnt-1] <= R[cnt]){
R[cnt-1] = L[cnt]-1;
}
}
}
int answer = n;
for(int i = 1; i <= n; i++){
B[i] += B[i-1];
if(B[i] == 0){
answer--;
}
}
gar[1] = 1;
for(int i = 2; i <= cnt; i++){
if(R[i] <= R[i-1]) gar[i] = gar[i-1]; else gar[i] = i;
}
shig[cnt] = cnt;
for(int i = cnt-1; i >= 1; i--){
if(R[i] >= R[i+1]) shig[i] = shig[i+1]; else shig[i] = i;
}
if(cnt <= d){
cout << cnt << endl;
return ;
}
for(int i = 1; i <= cnt; i++){
int daf = R[i] - L[i];
//cout << shig[i] << endl;
//cout << L[i] << " " << R[i] << " " << shig[i] << endl;
if(shig[i] != i) daf -= (R[i+1]-L[i+1]+1);
//cout << daf << endl;
upd(1,1,cnt,i,i,daf);
}
while(d--){
pair<int,int> p = mx[1];
int val = p.ff;
int ind = p.ss;
answer -= val;
//cout << val << " " << ind << endl;
if(fix[ind] == 1){
upd2(1,1,cnt,ind);
} else {
upd2(1,1,cnt,ind);
int val = R[ind]-R[shig[ind]];
if(val)upd(1,1,cnt,ind,shig[ind],-val);
if(gar[ind] < ind)upd1(1,1,cnt,gar[ind],ind-1);
for(int i = gar[ind]; i <= ind; i++){
fix[i] = 1;
}
}
}
cout << answer << endl;
}
main(){
ios::sync_with_stdio(0);
int T = 1;
//cin >> T;
for(int i = 1; i <= T; i++){
test_case();
}
}
컴파일 시 표준 에러 (stderr) 메시지
prison.cpp:175:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
175 | main(){
| ^~~~
# | 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... |