제출 #931361

#제출 시각아이디문제언어결과실행 시간메모리
931361hqminhuwu코끼리 (Dancing Elephants) (IOI11_elephants)C++14
100 / 100
5499 ms37100 KiB
#include <bits/stdc++.h> #define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a) #define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);) #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a) #define st first #define nd second #define ll long long #define ull unsigned long long #define pii pair <int,int> #define pll pair <ll,ll> #define piii pair <int,pii> #define vi vector <int> #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define file "test" using namespace std; const int nn = 5e5 + 5; const ll oo = 1e9; const ll mod = 1e9 + 7; const int uwu = 400; int nl, n; struct block { vector <pii> v; int cnt[2 * uwu + 1], pos[2 * uwu + 1]; void build (){ if (v.empty()) return; int r = v.size(); r--; cnt[r] = 1, pos[r] = v[r].st; ford (l, r, 0){ while (v[r].st - v[l].st > nl) r--; if (r == v.size() - 1) cnt[l] = 1, pos[l] = v[l].st; else cnt[l] = cnt[r + 1] + 1, pos[l] = pos[r + 1]; } } void ins (int val, int id){ v.pb({val, id}); int i = v.size(); i--; while (i > 0 && v[i] < v[i - 1]) swap(v[i], v[i - 1]), i--; } void ers (int id){ int j; forf (i, 0, v.size()) if (v[i].nd == id) j = i; forf (i, j, v.size() - 1) swap(v[i], v[i + 1]); v.pop_back(); } pii get (int u){ if (u + nl >= v.back().st) return {u, 0}; // cout << "get " << v.back().st << " " << v.back().nd << "\n"; int k = upper_bound(all(v), mp(u + nl, 1000000)) - v.begin(); return {pos[k], cnt[k]}; } void debug (){ // forf (i, 0, v.size()) // cout <<v[i].st << " " << v[i].nd << " " << cnt[i] << " " << pos[i] << "\n"; } }; block b[uwu + 1000]; pii a[nn]; int pos[nn], cnt; void rs (){ int j = 0; forr (i, 0, uwu) for (pii w : b[i].v) a[++j] = w; // forr (i, 1, n) // cout << a[i].st << " " << a[i].nd << "\n"; forr (i, 0, uwu) b[i].v.clear(); forr (i, 1, n) b[i / uwu].ins(a[i].st, a[i].nd), pos[a[i].nd] = i / uwu; forr (i, 0, uwu) b[i].build(), b[i].debug(); } void debug(){ forr (i, 0, uwu) cout << i << ":\n",b[i].debug(); } void init (int _n, int _l, int _x[]){ n = _n; nl = _l; forr (i, 1, n) a[i].st = _x[i - 1], a[i].nd = i; sort(a + 1, a + 1 + n); rs(); } int update (int u, int w){ //cout << L << "\n"; if (cnt > uwu) rs(), cnt = 0; cnt++; //return 0; int j = uwu; forr (i, 1, uwu){ if (b[i].v.empty()) { j = i - 1; break; } if (b[i].v[0].st > w){ j = i - 1; break; } } u++; b[pos[u]].ers(u); b[pos[u]].build(); b[j].ins(w, u); b[j].build(); pos[u] = j; //debug(); int d = 0, ans = 0; forr (i, 0, uwu) if (!b[i].v.empty()){ d = b[i].v[0].st; break; } forr (i, 0, uwu){ //cout << d << " " << ans << "\n"; if (b[i].v.empty()) continue; pii tmp = b[i].get(d); d = tmp.st; ans += tmp.nd; } return ans + 1; }

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

elephants.cpp: In member function 'void block::build()':
elephants.cpp:39:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    if (r == v.size() - 1)
      |        ~~^~~~~~~~~~~~~~~
elephants.cpp: In member function 'void block::ers(int)':
elephants.cpp:4:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
      |                                              ^
elephants.cpp:56:3: note: in expansion of macro 'forf'
   56 |   forf (i, 0, v.size())
      |   ^~~~
elephants.cpp:4:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
      |                                              ^
elephants.cpp:59:3: note: in expansion of macro 'forf'
   59 |   forf (i, j, v.size() - 1)
      |   ^~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:59:9: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |   forf (i, j, v.size() - 1)
      |         ^
elephants.cpp:55:7: note: 'j' was declared here
   55 |   int j;
      |       ^
#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...