제출 #136049

#제출 시각아이디문제언어결과실행 시간메모리
136049evpipis코끼리 (Dancing Elephants) (IOI11_elephants)C++11
100 / 100
5187 ms19896 KiB
//#define TEST #ifndef TEST #include "elephants.h" #endif // TEST #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back typedef pair<int, int> ii; const int len = 15e4+4; int n, l, k, rem; int hel[len], old[len]; struct bucket{ vector<int> vec; vector<ii> nex; void add(int v){ vec.insert(lower_bound(vec.begin(), vec.end(), v), v); upd(); } void del(int v){ vec.erase(lower_bound(vec.begin(), vec.end(), v)); upd(); } void upd(){ nex.resize(vec.size()); for (int i = (int)vec.size()-1, j = vec.size(); i >= 0; i--){ while (vec[i]+l+1 <= vec[j-1]) j--; if (j == vec.size()) nex[i] = mp(vec[i]+l+1, 1); else nex[i] = mp(nex[j].fi, nex[j].se+1); } } void print(){ for (int i = 0; i < vec.size(); i++) printf("%d ", vec[i]); printf("\n"); for (int i = 0; i < nex.size(); i++) printf("(%d, %d) ", nex[i].fi, nex[i].se); printf("\n"); } }; bucket data[len]; int fin(int v){ int l = 0, r = (n+k-1)/k-1, ans = -1; //printf("l = %d, r = %d\n", l, r); if (data[r].vec.empty()) r--; while (l <= r){ int mid = (l+r)/2; if (data[mid].vec.back() >= v) ans = mid, r = mid-1; else l = mid+1; } //printf("first bucket that contains element >= %d: %d\n", v, ans); return ans; } int update(int pos, int val){ data[fin(old[pos])].del(old[pos]); old[pos] = val; //printf("after del\n"); int hey = fin(val); if (hey == -1) hey = (n+k-1)/k-1; data[hey].add(val); rem--; //printf("after add\n"); /*printf("rem = %d, buckets =\n", rem); for (int i = 0; i*k < n; i++){ printf("bucket %d:\n", i); data[i].print(); }*/ //system("pause"); if (rem == 0){ for (int i = 0, x = 0; i*k < n; i++){ for (int j = 0; j < data[i].vec.size(); j++) hel[x++] = data[i].vec[j]; data[i].vec.clear(); } for (int i = 0; i*k < n; i++){ for (int j = i*k; j < min(n, (i+1)*k); j++) data[i].vec.pb(hel[j]); data[i].upd(); } rem = k-1; } /*printf("buckets after refresh\n"); for (int i = 0; i*k < n; i++){ printf("bucket %d:\n", i); data[i].print(); }*/ int ans = 0, cur = 0; while (true){ int b = fin(cur); if (b == -1) break; int p = lower_bound(data[b].vec.begin(), data[b].vec.end(), cur)-data[b].vec.begin(); ans += data[b].nex[p].se; cur = data[b].nex[p].fi; } return ans; } void init(int N, int L, int xs[]) { n = N, l = L, k = 1606, rem = k-1; //1606; for (int i = 0; i < n; i++) old[i] = xs[i]; //printf("bef\n"); for (int i = 0; i*k < n; i++){ for (int j = i*k; j < min((i+1)*k, n); j++) data[i].vec.pb(xs[j]); data[i].upd(); } //printf("after build\n"); /*for (int i = 0; i*k < n; i++){ printf("bucket %d:\n", i); data[i].print(); }*/ } #ifdef TEST int main(){ int N, L, xs[len], M; scanf("%d %d %d", &N, &L, &M); for (int i = 0; i < N; i++) scanf("%d", &xs[i]); init(N, L, xs); for (int i = 0; i < M; i++){ int a, b; scanf("%d %d", &a, &b); printf("%d\n", update(a, b)); } return 0; } #endif

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

elephants.cpp: In member function 'void bucket::upd()':
elephants.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (j == vec.size())
                 ~~^~~~~~~~~~~~~
elephants.cpp: In member function 'void bucket::print()':
elephants.cpp:48:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < vec.size(); i++)
                         ~~^~~~~~~~~~~~
elephants.cpp:52:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < nex.size(); i++)
                         ~~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:99:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < data[i].vec.size(); 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...