제출 #50039

#제출 시각아이디문제언어결과실행 시간메모리
50039Mamnoon_Siam코끼리 (Dancing Elephants) (IOI11_elephants)C++17
10 / 100
1076 ms23652 KiB
#include "elephants.h" //#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; #define debug(s) cout<< #s <<" = "<< s <<endl #define all(v) (v).begin(), (v).end() #define KeepUnique(v) (v).erase( unique(all(v)), v.end() ) #define MEMSET(a,val) memset(a, val, sizeof a) #define PB push_back #define endl '\n' inline int myrand(int l, int r) { int ret = rand(); ret <<= 15; ret ^= rand(); if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l; return ret; } template <typename F, typename S> ostream& operator << (ostream& os, const pair< F, S>& p) { return os<<"(" <<p.first<<", "<<p.second<<")"; } typedef pair<int, int> ii; template<typename T> using min_pq = priority_queue<T, vector<T>, greater<T> >; const int maxn = 150005; const int magic = 50; int n, L; vector<int> X, to; multiset<int> ms; int mx_blk, upd_cnt, where[maxn]; vector<int> input[510]; struct bucket { vector<int> x, cnt, last; bucket() {} void prepare() { if(x.size() == 0) return; //cout << "in" << endl; assert(last.size()); assert(x.size()); assert(cnt.size()); last[last.size()-1] = x[x.size()-1] + L - 1, cnt[cnt.size()-1] = 1; for(int l = x.size() - 2, r = x.size() - 1; l >= 0; l--) { while(x[r] > x[l] + L - 1) r--, assert(r >= 0); if(r == x.size() - 1) cnt[l] = 1, last[l] = x[l] + L - 1; else cnt[l] = cnt[r + 1] + 1, last[l] = last[r + 1]; } } void assign(vector<int> &v) { x = v; cnt.resize(v.size()), last.resize(v.size()); prepare(); } void insert(int _x) { x.insert(lower_bound(all(x), _x), _x); //cout << "another voila" << endl; //debug(x.size()); //for(int b : x) cout << b << ' '; cout << endl; //cnt.push_back(0); //last.push_back(0); cnt.resize(x.size()); last.resize(x.size()); //cout << "hehe" << endl; prepare(); } void erase(int _x) { assert(x.size()); auto it = find(all(x), _x); assert(it != x.end()); x.erase(it); last.pop_back(), cnt.pop_back(); prepare(); } ii cnt_last(int _x) { int it = upper_bound(all(x), _x) - x.begin(); if(it == x.size()) { return ii(0, _x); } return ii(cnt[it], last[it]); } void print() { for(int b : x) cout << b << ' '; cout << endl; for(int b : cnt) cout << b << ' '; cout << endl; for(int b : last) cout << b << ' '; cout << endl; } }; bucket chunk[510]; void refresh() { //cout << "refreshing" << endl; upd_cnt = 0; vector<int> temp(X.size()); for(int i = 0; i < X.size(); i++) temp[i] = X[to[i]]; for(int i = 0; i < X.size(); i++) to[i] = i; sort(all(to), [&temp](int p, int q){ return temp[p] < temp[q]; }); X.clear(); for(int b : ms) X.push_back(b); for(int i = 0; i <= mx_blk; i++) input[i].clear(); for(int i = 0; i < X.size(); i++) { input[i / magic].push_back(X[i]); where[i] = i / magic; } for(int i = 0; i <= mx_blk; i++) { chunk[i].assign(input[i]); } } void init(int _n, int _L, int _X[]) { n = _n, L = _L; L++; X.resize(n); for(int i = 0; i < n; i++) { X[i] = _X[i]; ms.insert(X[i]); } to.resize(n); for(int i = 0; i < n; i++) to[i] = i; mx_blk = (X.size() - 1) / magic; refresh(); } int update(int i, int y) { //cout << "Starting ........ " << endl; ms.erase(ms.find(X[i])); //cout << "again" << endl; //debug(where[i]); chunk[where[i]].erase(X[i]); //cout << "crossed" << endl; for(int j = 0; j <= mx_blk; j++) { //cout << "pre = " << j << endl; //debug(chunk[j].x.size()); if(chunk[j].x.size() == 0) { //cout << "going to hell" << endl; goto hell; } //cout << "mid" << endl; if(y <= chunk[j].x.back()) { //cout << "yahoooo" << endl; //debug(chunk[j].x.size()); chunk[j].insert(y); //cout << "found" << endl; where[i] = j; //cout << "been here" << endl; break; } hell : ; //cout << "J = " << j << endl; if(j == mx_blk) { //cout << "here" << endl; chunk[j].insert(y); where[i] = j; } } //cout << "voila" << endl; ms.insert(y); X[i] = y; //cout << endl << "New Update" << endl; if(false) { for(int b : ms) cout << b << ' '; cout << endl; for(int i = 0; i <= mx_blk; i++) { cout << i << " :: " << endl; chunk[i].print(); } } //cout << "finished Printing" << endl; int ret = 0, now = -1; for(int i = 0; i <= mx_blk; i++) { ii cur = chunk[i].cnt_last(now); //cout << cur << ' '; ret += cur.first; now = cur.second; } //cout << endl; upd_cnt++; if(upd_cnt == magic) { refresh(); } //cout << "here" << endl; return ret; }

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

elephants.cpp: In function 'int myrand(int, int)':
elephants.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
elephants.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
elephants.cpp: In member function 'void bucket::prepare()':
elephants.cpp:49:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(r == x.size() - 1) cnt[l] = 1, last[l] = x[l] + L - 1;
       ~~^~~~~~~~~~~~~~~
elephants.cpp: In member function 'ii bucket::cnt_last(int)':
elephants.cpp:79:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(it == x.size()) { return ii(0, _x); }
      ~~~^~~~~~~~~~~
elephants.cpp: In member function 'void bucket::print()':
elephants.cpp:83:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int b : x) cout << b << ' '; cout << endl;
   ^~~
elephants.cpp:83:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int b : x) cout << b << ' '; cout << endl;
                                    ^~~~
elephants.cpp:84:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int b : cnt) cout << b << ' '; cout << endl;
   ^~~
elephants.cpp:84:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int b : cnt) cout << b << ' '; cout << endl;
                                      ^~~~
elephants.cpp:85:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int b : last) cout << b << ' '; cout << endl;
   ^~~
elephants.cpp:85:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int b : last) cout << b << ' '; cout << endl;
                                       ^~~~
elephants.cpp: In function 'void refresh()':
elephants.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++) temp[i] = X[to[i]];
                 ~~^~~~~~~~~~
elephants.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++) to[i] = i;
                 ~~^~~~~~~~~~
elephants.cpp:101:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++) {
                 ~~^~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:170:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int b : ms) cout << b << ' '; cout << endl;
   ^~~
elephants.cpp:170:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int b : ms) cout << b << ' '; cout << 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...