제출 #1028604

#제출 시각아이디문제언어결과실행 시간메모리
1028604ngrace코끼리 (Dancing Elephants) (IOI11_elephants)C++14
100 / 100
6538 ms27552 KiB
#include <bits/stdc++.h> #include "elephants.h" using namespace std; #define v vector #define ii pair<int,int> #define fi first #define se second const int MAXN = 150000; int N, L; v<int> E; void init(int n, int l, int X[]) { N = n; L = l; for(int i=0; i<N; i++) E.push_back(X[i]); } const int BUCK = 400; int qNum = 0; v<int> buckInd(MAXN); v<v<ii>> bucks(MAXN/BUCK + 1); v<v<ii>> bucksAns(MAXN/BUCK+1); void rebuildBuck(int b){ bucksAns[b].resize(bucks[b].size(), {0,0}); for(int i=bucks[b].size()-1; i>=0; i--){ auto it = lower_bound(bucks[b].begin()+i+1, bucks[b].end(), make_pair(bucks[b][i].fi+L+1, -1)); if(it==bucks[b].end()) bucksAns[b][i] = {1, bucks[b][i].fi+L+1}; else{ ii tmp = bucksAns[b][distance(bucks[b].begin(), it)]; bucksAns[b][i] = {1 + tmp.fi, tmp.se}; } } } void rebuild(){ v<ii> e; for(int i=0; i<N; i++) e.push_back({E[i], i}); sort(e.begin(), e.end()); for(int i=0; i<bucks.size(); i++) bucks[i].clear(); int b=0; for(auto it:e){ if(bucks[b].size()==BUCK) b++; bucks[b].push_back(it); buckInd[it.se] = b; } for(int i=0; i<bucks.size(); i++) rebuildBuck(i); } void move(int e, int x){ int b = buckInd[e]; bucks[b].erase(find(bucks[b].begin(), bucks[b].end(), make_pair(E[e], e))); rebuildBuck(b); E[e] = x; int l=0, r=bucks.size()-1; while(l<r){ int m=(l+r+1)/2; if(bucks[m].size()>0 && bucks[m][0].fi<=x) l=m; else r=m-1; } auto it = upper_bound(bucks[l].begin(), bucks[l].end(), make_pair(x, e)); bucks[l].insert(it, {x, e}); buckInd[e] = l; rebuildBuck(l); } int ans(){ int cur = 0; int ret = 0; for(int b=0; b<bucks.size(); b++){ auto it = lower_bound(bucks[b].begin(), bucks[b].end(), make_pair(cur, -1)); if(it!=bucks[b].end()){ int i = distance(bucks[b].begin(), it); ret += bucksAns[b][i].fi; cur = bucksAns[b][i].se; } } return ret; } void debug(int b){ for(int i=0; i<bucks[b].size(); i++) cout<<bucks[b][i].fi<<" "<<bucks[b][i].se<<" "<<bucksAns[b][i].fi<<" "<<bucksAns[b][i].se<<endl; cout<<endl; } int update(int i, int y){ if((qNum++)%BUCK==0) rebuild(); move(i, y); return ans(); }

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

elephants.cpp: In function 'void rebuild()':
elephants.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0; i<bucks.size(); i++) bucks[i].clear();
      |                  ~^~~~~~~~~~~~~
elephants.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0; i<bucks.size(); i++) rebuildBuck(i);
      |                  ~^~~~~~~~~~~~~
elephants.cpp: In function 'int ans()':
elephants.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int b=0; b<bucks.size(); b++){
      |                  ~^~~~~~~~~~~~~
elephants.cpp: In function 'void debug(int)':
elephants.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0; i<bucks[b].size(); i++) cout<<bucks[b][i].fi<<" "<<bucks[b][i].se<<" "<<bucksAns[b][i].fi<<" "<<bucksAns[b][i].se<<endl;
      |                  ~^~~~~~~~~~~~~~~~
#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...