제출 #418728

#제출 시각아이디문제언어결과실행 시간메모리
418728Hegdahl코끼리 (Dancing Elephants) (IOI11_elephants)C++17
10 / 100
2 ms460 KiB
#include <bits/stdc++.h> #include "elephants.h" #define ar array using namespace std; const int mxN = 15e4; int n, l, R, a[mxN], idxs[mxN], where[mxN]; struct Chunk { int size; vector<int> xs; vector<ar<int, 2>> dp; Chunk(vector<int> &&_xs) : size((int)_xs.size()), xs(move(_xs)) { dp.resize(size); recalc(); } void recalc() { for (int i = size-1; i >= 0; --i) { int j = lower_bound(xs.begin(), xs.end(), xs[i]+l) - xs.begin(); if (j == size) dp[i] = {1, xs[i]+l}; else dp[i] = {dp[j][0]+1, dp[j][1]}; } } void insert(int x) { ++size; auto it = upper_bound(xs.begin(), xs.end(), x); xs.insert(it, x); recalc(); } void erase(int x) { --size; auto it = lower_bound(xs.begin(), xs.end(), x); assert(it != xs.end()); xs.erase(it); recalc(); } ar<int, 2> qry(int x) { int j = lower_bound(xs.begin(), xs.end(), x) - xs.begin(); if (j == size) return {0, x}; return dp[j]; } }; vector<Chunk> chunks; void recalc() { iota(idxs, idxs+n, 0); sort(idxs, idxs+n, [&](int i, int j){ return a[i] < a[j]; }); chunks.clear(); for (int i0 = 0; i0 < n; i0 += R) { vector<int> xs; for (int i = i0; i < min(i0+R, n); ++i) { xs.push_back(a[idxs[i]]); where[idxs[i]] = chunks.size(); } chunks.emplace_back(move(xs)); } } void init(int N, int L, int X[]) { n = N, l = L+1; for (int i = 0; i < n; ++i) a[i] = X[i]; R = sqrt(N); recalc(); } int solve() { int x = -1e9-10, ans = 0; for (int c = 0; c < chunks.size(); ++c) { auto [used, new_x] = chunks[c].qry(x); ans += used; x = new_x; } return ans; } int update(int i, int y) { static int update_cnt = 0; if (++update_cnt%R == 0) { a[i] = y; recalc(); } else { int c = where[i]; chunks[c].erase(a[i]); a[i] = y; for (c = 1; c < chunks.size(); ++c) if (chunks[c].size && chunks[c].xs[0] > a[i]) break; --c; chunks[c].insert(a[i]); where[i] = c; } return solve(); }

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

elephants.cpp: In function 'int solve()':
elephants.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Chunk>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (int c = 0; c < chunks.size(); ++c) {
      |                   ~~^~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Chunk>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (c = 1; c < chunks.size(); ++c)
      |                 ~~^~~~~~~~~~~~~~~
#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...