이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=150050,inf=1e9;
int koren=400;
int n,a[N+50],b[N+50],L,res,nq,dp[600][2500],poslednji[600][2500];
int A[600][2500],sajz[600];
void Calcblok(int i){
if(sajz[i]==0) return;
for(int j=sajz[i]-1,k=sajz[i]-1;j>=0;j--){
while(k>=1 && A[i][j]+L<A[i][k-1]) k--;
if(A[i][j]+L>=A[i][sajz[i]-1]){
dp[i][j]=1;
poslednji[i][j]=j;
}
else{
dp[i][j]=1+dp[i][k];
poslednji[i][j]=poslednji[i][k];
}
}
}
void Erase(int x){
for(int i=0;i<=(n-1)/koren;i++){
if(sajz[i]==0) continue;
if(A[i][0]<=x && x<=A[i][sajz[i]-1]){
int ind=sajz[i];
for(int j=0;j<sajz[i];j++) if(A[i][j]==x) ind=j;
while(ind+1<sajz[i]){swap(A[i][ind],A[i][ind+1]);ind++;}
sajz[i]--;
Calcblok(i);
break;
}
}
}
void Insert(int x){
for(int i=0;i<=(n-1)/koren;i++){
if(sajz[i]==0) continue;
/*int l=0,r=inf;
for(int j=i-1;j>=0;j--) if(!A[j].empty()){l=A[j].back();break;}
for(int j=i+1;j<=i+5;j++) if(!A[j].empty()){r=A[j][0];break;}*/
if(A[i][0]<=x && x<=A[i][sajz[i]-1] || (x<=A[i][0]) || (i==(n-1)/koren)){
sajz[i]++;
A[i][sajz[i]-1]=x;
int ind=sajz[i]-1;
while(ind>=1 && A[i][ind]<A[i][ind-1]){swap(A[i][ind],A[i][ind-1]);ind--;}
Calcblok(i);
break;
}
}
}
void Calc(){
//for(int i=0;i<=(n-1)/koren;i++) A[i].clear();
for(int i=0;i<n;i++){
A[i/koren][i%koren]=b[i];
sajz[i/koren]=i%koren+1;
}
for(int i=0;i<=(n-1)/koren;i++) Calcblok(i);
}
int Resi(){
int res=0,x=-1;
for(int i=0;i<=(n-1)/koren;i++){
if(sajz[i]==0) continue;
if(x<=A[i][sajz[i]-1]){
int ind=0;
for(int j=sajz[i]-1;j>=0;j--) if(A[i][j]>=x) ind=j;
res+=dp[i][ind];
x=A[i][poslednji[i][ind]]+L+1;
}
}
return res;
}
void init(int N1, int L1, int X[]){
n = N1;
for(int i=0;i<n;i++) a[i]=X[i];
for(int i=0;i<n;i++) b[i]=a[i];
sort(b,b+n);
L=L1;
//for(int i=0;i<koren+50;i++) A[i].reserve(3*koren+10);
Calc();
//for(int i=0;i<=(n-1)/koren;i++) printf("%i ",sajz[i]);
}
int update(int qind, int y){
Erase(a[qind]);
for(int i=n-1;i>=0;i--){
if(b[i]==a[qind]){
for(int j=i+1;j<n;j++) b[j-1]=b[j];
break;
}
}
a[qind]=y;
Insert(a[qind]);
b[n-1]=a[qind];
for(int j=n-1;j>=1;j--){
if(b[j-1]>b[j]) swap(b[j-1],b[j]);
else break;
}
nq++;
if(nq==koren-5) {Calc();nq=0;}
return Resi();
}
컴파일 시 표준 에러 (stderr) 메시지
elephants.cpp: In function 'void Insert(int)':
elephants.cpp:46:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
46 | if(A[i][0]<=x && x<=A[i][sajz[i]-1] || (x<=A[i][0]) || (i==(n-1)/koren)){
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# | 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... |