제출 #391723

#제출 시각아이디문제언어결과실행 시간메모리
391723iANikzad코끼리 (Dancing Elephants) (IOI11_elephants)C++17
0 / 100
2 ms596 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define F first #define S second #define debug(x) cerr<<#x<<" :"<<x<<"\n" #define all(x) x.begin(),x.end() #define pii pair<int,int> #define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie(); //#define int long long typedef long long ll; typedef long double ld; const int maxn = 1.5e5 + 7; const int mod = 1e9 + 7; const int INF = 2e9 + 7; const int mlog = 20; const int SQRT = 400; int n, k; int bcnt; int R[SQRT + 7]; int pos[maxn]; map<int, int> mp; vector<int> jump[SQRT + 7], cnt[SQRT + 7], bucket[SQRT + 7]; void solve(int ind) { jump[ind] = vector<int>(bucket[ind].size()); cnt[ind] = vector<int>(bucket[ind].size()); for(int i = bucket[ind].size() - 1, j = bucket[ind].size(); ~i; i--) { while(bucket[ind][j - 1] > bucket[ind][i] + k) j--; if(j < (int)bucket[ind].size()) jump[ind][i] = jump[ind][j], cnt[ind][i] = cnt[ind][j] + 1; else jump[ind][i] = bucket[ind][i] + k, cnt[ind][i] = 1; } } void add(int x, bool rmv) { int ptr = -1; while(R[++ptr] < x); int ind = lower_bound(bucket[ptr].begin(), bucket[ptr].end(), x) - bucket[ptr].begin(); if(rmv) bucket[ptr].erase(bucket[ptr].begin() + ind); else bucket[ptr].insert(bucket[ptr].begin() + ind, x); solve(ptr); } void REBUILD() { bcnt = 0; for(pii p : mp) { if(!bcnt || bucket[bcnt - 1].size() >= SQRT) bucket[bcnt++].clear(); bucket[bcnt - 1].pb(p.F); } for(int i = 0; i < bcnt; i++) { if(i < bcnt - 1) R[i] = bucket[i + 1][0] - 1; else R[i] = +INF; solve(i); } } void init(int _n, int _k, int X[]) { n = _n, k = _k; for(int i = 0; i < n; i++) ++mp[pos[i] = X[i]]; } int cntBLOCK; int update(int i,int y) { if(cntBLOCK++ % SQRT == 0) REBUILD(); if(!--mp[pos[i]]) add(pos[i], 0), mp.erase(pos[i]); if(!mp[y]) add(y, 1); mp[y]++, pos[i] = y; int ans = 0, cur = -1; for(int i = 0; i < bcnt; i++) { int ind = upper_bound(bucket[i].begin(), bucket[i].end(), cur) - bucket[i].begin(); if(ind < bucket[i].size()) ans += cnt[i][ind], cur = jump[i][ind]; } return ans; }

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

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:101:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         if(ind < bucket[i].size())
      |            ~~~~^~~~~~~~~~~~~~~~~~
#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...