Submission #13795

#TimeUsernameProblemLanguageResultExecution timeMemory
13795gs14004Dancing Elephants (IOI11_elephants)C++14
Compilation error
0 ms0 KiB
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int U = 1500; // 400 ~ 1500 const int B = 1500; // 400 ~ 1500 struct elem{ int val; int next; int cnt; }; bool operator<(elem a, elem b){ return a.val < b.val; } vector<elem> bucket[105]; int sentinel; int b[150005]; int a[150005], n, l; int q_cnt; void make_arr(){ int piv = 0; for (int i=0; i<sentinel; i++) { for (int j=0; j<bucket[i].size(); j++) { b[piv++] = bucket[i][j].val; } } } void bucket_label(int bnum){ int pt = (int)bucket[bnum].size(); for (int i=(int)bucket[bnum].size()-1; i>=0; i--) { while (pt && bucket[bnum][pt-1].val > bucket[bnum][i].val + l) { pt--; } if(pt == bucket[bnum].size()){ bucket[bnum][i].next = -1; bucket[bnum][i].cnt = 0; } else{ if(bucket[bnum][pt].next == -1){ bucket[bnum][i].next = pt; } else{ bucket[bnum][i].next = bucket[bnum][pt].next; } bucket[bnum][i].cnt = bucket[bnum][pt].cnt + 1; } } } void bucket_clear(){ for (int i=0; i<sentinel; i++) { bucket[i].clear(); int piv = min(n-i*B,B); bucket[i].resize(piv); for (int j=0; j<piv; j++) { bucket[i][j].val = b[i*B + j]; } bucket_label(i); } } void bucket_erase(int bnum, int pos){ for (int i=pos; i<bucket[bnum].size()-1; i++) { bucket[bnum][i] = bucket[bnum][i+1]; } bucket[bnum].pop_back(); bucket_label(bnum); } void bucket_update(int bnum, int pos, int val){ bucket[bnum].push_back((elem){0,0,0}); for (int i=(int)bucket[bnum].size()-1; i>pos; i--) { bucket[bnum][i] = bucket[bnum][i-1]; } bucket[bnum][pos].val = val; bucket_label(bnum); } int query(){ int pos = 0, ret = 0; for (int i=0; i<sentinel; ) { if(bucket[i].empty()){ i++; continue; } ret += bucket[i][pos].cnt + 1; if(bucket[i][pos].next != -1) pos = bucket[i][pos].next; int new_buck = i+1; int new_pos = bucket[i][pos].val + l; while (1){ if(new_buck == sentinel) break; if(lower_bound(bucket[new_buck].begin(),bucket[new_buck].end(),(elem){new_pos+1,0,0}) != bucket[new_buck].end()) break; new_buck++; } if(new_buck == sentinel) break; i = new_buck; pos = (int)(lower_bound(bucket[new_buck].begin(),bucket[new_buck].end(),(elem){new_pos+1,0,0}) - bucket[new_buck].begin()); } return ret; } void init(int N, int L, int* X){ memcpy(a,X,sizeof(int) * N); memcpy(b,a,sizeof(int) * N); n = N; l = L; while (sentinel * B < n) sentinel++; bucket_clear(); } int update(int i, int y){ q_cnt = (q_cnt + 1) % U; int o = a[i]; a[i] = y; for (int i=0; i<sentinel; i++) { if(bucket[i].empty()) continue; else if(bucket[i][0].val <= o && o <= bucket[i].back().val){ int pos = (int)(lower_bound(bucket[i].begin(),bucket[i].end(),(elem){o,0,0}) - bucket[i].begin()); bucket_erase(i,pos); break; } } /****** insert y ******/ int low = -1; for (int i=0; i<sentinel; i++) { if(bucket[i].empty()) continue; if(bucket[i][0].val <= y) low = i; } if(low == -1){ bucket_update(0,0,y); } else{ int pos = (int)(lower_bound(bucket[low].begin(),bucket[low].end(),(elem){y,0,0}) - bucket[low].begin()); bucket_update(low,pos,y); } if(q_cnt == 0){ make_arr(); bucket_clear(); } return query(); } int main(){ int n,l,m,p[150005]; scanf("%d %d %d",&n,&l,&m); for (int i=0; i<n; i++) { scanf("%d",&p[i]); } init(n,l,p); for (int i=0; i<m; i++) { int a,b; scanf("%d %d",&a,&b); printf("%d\n",update(a,b)); } }

Compilation message (stderr)

elephants.cpp: In function ‘void make_arr()’:
elephants.cpp:28:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<bucket[i].size(); j++) {
                        ^
elephants.cpp: In function ‘void bucket_label(int)’:
elephants.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pt == bucket[bnum].size()){
               ^
elephants.cpp: In function ‘void bucket_erase(int, int)’:
elephants.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=pos; i<bucket[bnum].size()-1; i++) {
                      ^
elephants.cpp: In function ‘int main()’:
elephants.cpp:156:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&n,&l,&m);
                               ^
elephants.cpp:158:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
                          ^
elephants.cpp:163:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
                             ^
/tmp/ccnFu56e.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccn7Xg3z.o:elephants.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status