제출 #549896

#제출 시각아이디문제언어결과실행 시간메모리
549896neki코끼리 (Dancing Elephants) (IOI11_elephants)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; #define vc vector #define ps push_back const int mm=350; int n, l; struct e{ int i, pos, val, odsek, kok; e(int i_, int pos_): i(i_), pos(pos_){} bool operator<(const e& oth){return pos < oth.pos;} }; vc<e> es; vc<vc<e*>> dp; void calcdp(vc<e*>& arr){ int siz=arr.size(), nas=siz; for(int i=siz-1;i>=0;--i){ while((*arr[i]).pos+l<= (*arr[nas-1]).pos) --nas; if(nas<siz) (*arr[i]).val=(*arr[nas]).val, (*arr[i]).kok=(*arr[nas]).kok + 1; else (*arr[i]).val=(*arr[i]).pos+l, (*arr[i]).kok=1; } } void build(){ vc<e*> vsi; for(auto v : dp) for(auto u : v ) vsi.push_back(u); dp.clear(); for(int ods=0;ods<n;ods+=mm){ vc<e*> nods; for(int i=ods;i<min(n, ods+mm);++i){(*vsi[i]).odsek=ods;nods.ps(vsi[i]);} calcdp(nods); dp.ps(nods); } } void init(int N, int L, int* X){ n=N, l=L+1; for(int i=0;i<n;++i) es.ps(e(i, X[i])); dp.ps({}); for(int i=0;i<n;++i)dp[0].ps(&es[i]); build(); } void printdp(){ for(auto&& u:dp){ for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl; } } int update(int ind, int y){ es[ind].pos=y; int nov; for(int i=0;i<dp.size();++i) if(y<(*(dp[i].back())).pos){nov=i;break;} int star = es[ind].odsek; if(nov!=star){ vc<e*> shrani=dp[star]; dp[star].clear(); for(auto v : shrani) if((*v).i != ind) dp[star].ps(v); calcdp(dp[star]); dp[nov].ps(&es[ind]); } //printdp(); sort(dp[nov].begin(), dp[nov].end(), [](e* a, e* b){ return *a<*b; }); calcdp(dp[nov]); printdp(); int curpos=-1, ret=0; for(auto&& v: dp) if(curpos<=(*(v.back())).pos){ int L=0, R=v.size()-1; //nani while(L<R){ int mid=(L+R)/2; if(curpos <= (*v[mid]).pos) R=mid; else L=mid+1; } curpos= (*v[L]).val; ret+= (*v[L]).kok; } return ret; }

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

elephants.cpp: In function 'void printdp()':
elephants.cpp:55:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   55 |         for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
      |         ^~~
elephants.cpp:55:82: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   55 |         for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
      |                                                                                  ^~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<e*> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     int nov; for(int i=0;i<dp.size();++i) if(y<(*(dp[i].back())).pos){nov=i;break;}
      |                          ~^~~~~~~~~~
elephants.cpp:70:15: warning: 'nov' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |         dp[nov].ps(&es[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...