제출 #391758

#제출 시각아이디문제언어결과실행 시간메모리
391758sinamhdv코끼리 (Dancing Elephants) (IOI11_elephants)C++11
50 / 100
5703 ms4308 KiB
// IOI11_elephants #include "elephants.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod = 1000 * 1000 * 1000 + 7; const int INF = 1e9 + 100; const ll LINF = 1e18 + 100; #ifdef DEBUG #define dbg(x) cout << #x << " = " << (x) << endl << flush; #define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; } #else #define dbg(x) ; #define dbgr(s, f) ; #endif #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define all(x) (x).begin(), (x).end() #define pb push_back #define mp make_pair #define fr first #define sc second #define endl '\n' #define MAXN 150100 #define SQ 270 #define BLK (MAXN / SQ + 10) int n, L; vector<int> blk[BLK]; int bnum[MAXN], blkind[MAXN]; int pos[MAXN], ind[MAXN]; pii dp[MAXN]; int qnum; int bcnt; inline bool cmp(int x, int y) { return pos[x] < pos[y]; } inline void prep_dp(int b) { for (int i = (int)blk[b].size() - 1; i >= 0; i--) { int u = blk[b][i]; int nxt = pos[u] + L; if (nxt >= pos[blk[b].back()]) dp[u] = {1, nxt}; else { pos[MAXN - 1] = nxt; int nu = *upper_bound(all(blk[b]), MAXN - 1, cmp); dp[u] = dp[nu]; dp[u].fr++; } } } inline void rebuild(void) { int ptr = 0; FOR(i, 0, BLK) { for (int u : blk[i]) ind[ptr++] = u; blk[i].clear(); } FOR(i, 0, n) blk[i/SQ].pb(ind[i]), bnum[ind[i]] = i/SQ, blkind[ind[i]] = i % SQ; FOR(i, 0, bcnt) prep_dp(i); } void init(int N, int L, int X[]) { n = N; ::L = L; bcnt = (n - 1) / SQ + 1; copy(X, X + n, pos); iota(ind, ind + n, 0); FOR(i, 0, BLK) blk[i].reserve(2 * SQ + 10); rebuild(); } inline int blocklb(int x) { int l = -1, r = bcnt - 1; if (pos[blk[r].back()] < x) return INF; while (r - l > 1) { int mid = (r + l) / 2; if (pos[blk[mid].back()] < x) l = mid; else r = mid; } return r; } inline int person_ub(int x) { int b = blocklb(x + 1); if (b >= INF) return INF; pos[MAXN - 1] = x; return *upper_bound(all(blk[b]), MAXN - 1, cmp); } inline void swapadj(int b, int i) { blkind[blk[b][i - 1]]++; blkind[blk[b][i]]--; swap(blk[b][i], blk[b][i - 1]); } int update(int i, int y) { qnum++; if (qnum % (SQ - 5) == 0) rebuild(); // update blocks int old = bnum[i]; int nw = blocklb(y); if (nw >= INF) nw = bcnt - 1; pos[i] = y; bnum[i] = nw; FOR(j, blkind[i] + 1, (int)blk[old].size()) blkind[blk[old][j]]--; blk[old].erase(blk[old].begin() + blkind[i]); blk[nw].pb(i); blkind[i] = blk[nw].size() - 1; while (blkind[i] && y < pos[blk[nw][blkind[i] - 1]]) swapadj(nw, blkind[i]); // re-calc dp prep_dp(old); prep_dp(nw); // get answer int ans = 0; int p = blk[0][0]; while (p < n) { ans += dp[p].fr; p = person_ub(dp[p].sc); } return ans; }
#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...