제출 #1089055

#제출 시각아이디문제언어결과실행 시간메모리
1089055StefanSebez코끼리 (Dancing Elephants) (IOI11_elephants)C++14
97 / 100
9056 ms24660 KiB
#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],L,res,nq,dp[1500][1500],poslednji[1500][1500]; vector<int>A[N]; void Calcblok(int i){ if(A[i].empty()) return; for(int j=A[i].size()-1,k=A[i].size()-1;j>=0;j--){ while(k>=1 && A[i][j]+L<A[i][k-1]) k--; if(A[i][j]+L>=A[i].back()){ 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<koren+50;i++){ if(A[i].empty()) break; if(A[i][0]<=x && x<=A[i].back()){ int ind=A[i].size(); for(int j=0;j<A[i].size();j++) if(A[i][j]==x) ind=j; while(ind+1<A[i].size()){swap(A[i][ind],A[i][ind+1]);ind++;} A[i].pop_back(); Calcblok(i); break; } } } void Insert(int x){ for(int i=0;i<koren+50;i++){ if(A[i].empty()) break; int l=0,r=inf; if(i>=1) l=A[i-1].back(); if(!A[i+1].empty()) r=A[i+1][0]; if(l<=x && x<=r){ A[i].pb(x); int ind=A[i].size()-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(){ int b[n+10];for(int i=0;i<n;i++) b[i]=a[i]; sort(b,b+n); for(int i=0;i<=koren+50;i++) A[i].clear(); for(int i=0;i<n;i++) A[i/koren].pb(b[i]); for(int i=0;i<koren+50;i++) Calcblok(i); } void init(int N1, int L1, int X[]){ n = N1; for(int i=0;i<n;i++) a[i]=X[i]; L=L1; Calc(); for(int i=0;i<50;i++){ if(A[i].empty())break; /*for(auto j:A[i]) printf("%i ",j);printf("\n"); for(int j=0;j<A[i].size();j++) printf("%i ",dp[i][j]);printf("\n"); for(int j=0;j<A[i].size();j++) printf("%i ",poslednji[i][j]);printf("\n");*/ } } int update(int qind, int y){ Erase(a[qind]); a[qind]=y; Insert(a[qind]); nq++; if(nq>=koren) {Calc();nq-=koren;} /*printf("\n"); for(int i=0;i<koren+50;i++){ if(A[i].empty())break; for(auto j:A[i]) printf("%i ",j);printf("\n"); } printf("\n");*/ int res=0; int x=A[0][0]; //printf("da\n"); for(int i=0;i<koren+50;i++){ //printf("%i ",x); if(A[i].empty()) break; if(x<=A[i].back()){ int ind=0; for(int j=A[i].size()-1;j>=0;j--) if(A[i][j]>=x) ind=j; res+=dp[i][ind]; x=A[i][poslednji[i][ind]]+L+1; } } //printf("\n"); return res; }

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'void Erase(int)':
elephants.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for(int j=0;j<A[i].size();j++) if(A[i][j]==x) ind=j;
      |                ~^~~~~~~~~~~~
elephants.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    while(ind+1<A[i].size()){swap(A[i][ind],A[i][ind+1]);ind++;}
      |          ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...