Submission #809696

#TimeUsernameProblemLanguageResultExecution timeMemory
809696QwertyPiRope (JOI17_rope)C++14
80 / 100
2568 ms91608 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 1e6 + 11; int c[MAXN]; vector<int> ci[MAXN]; bool in[MAXN]; int n, m; int a[MAXN], cnt[MAXN], cnt2[MAXN]; int c1, c2; struct BIT{ int bit[MAXN]; void add(int p, int v){ p++; for(int i = p; i < MAXN; i += i & -i) bit[i] += v; } int qry(int p){ p++; int r = 0; for(int i = p; i; i -= i & -i) r += bit[i]; return r; } int search(int v){ int r = 0, s = 0; for(int j = 19; j >= 0; j--) if(r + (1 << j) < MAXN && s + bit[r + (1 << j)] <= v) s += bit[r + (1 << j)], r += (1 << j); return r; } } bit; void add(int x){ bit.add(cnt[x], -1); cnt[x]++; bit.add(cnt[x], 1); } void rem(int x){ bit.add(cnt[x], -1); cnt[x]--; bit.add(cnt[x], 1); } void build(int c[]){ cnt2[0] = m; bit.add(0, m); for(int i = 0; i < n; i++) add(c[i]); } void upd(int pos, int val){ add(val); rem(a[pos]); a[pos] = val; } int qry(int except){ int p1 = bit.search(m - 1), p2 = bit.search(m - 2); return cnt[except] == p1 ? p2 : p1; } bool in_range(int id){ return 0 <= id && id < n; } int32_t main(){ cin.tie(0); cout.tie(0)->sync_with_stdio(false); cin >> n >> m; for(int i = 0; i < n; i++){ cin >> c[i]; c[i]--; ci[c[i]].push_back(i); a[i] = c[i]; } build(c); for(int i = 0; i < m; i++){ vector<int> revert; for(auto j : ci[i]) in[j] = true; // even index start int sz = ci[i].size(), l = 0, r = sz - 1; for(int k = l; k <= r; k++) { int j = ci[i][k]; int nxt = j ^ 1; if(in_range(nxt) && !in[nxt]) revert.push_back(nxt), upd(nxt, i), in[nxt] = true; } int q1 = n - qry(i) - sz; for(auto j : revert) in[j] = false, upd(j, c[j]); revert.clear(); // odd index start for(int k = l; k <= r; k++) { int j = ci[i][k]; int nxt = ((j + 1) ^ 1) - 1; if(in_range(nxt) && !in[nxt]) revert.push_back(nxt), upd(nxt, i), in[nxt] = true; } int q2 = n - qry(i) - sz; for(auto j : revert) in[j] = false, upd(j, c[j]); revert.clear(); int ans = min(q1, q2); cout << ans << endl; for(auto j : ci[i]) in[j] = false; } }

Compilation message (stderr)

rope.cpp: In function 'int32_t main()':
rope.cpp:68:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   68 |         for(auto j : revert) in[j] = false, upd(j, c[j]); revert.clear();
      |         ^~~
rope.cpp:68:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   68 |         for(auto j : revert) in[j] = false, upd(j, c[j]); revert.clear();
      |                                                           ^~~~~~
rope.cpp:78:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |         for(auto j : revert) in[j] = false, upd(j, c[j]); revert.clear();
      |         ^~~
rope.cpp:78:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   78 |         for(auto j : revert) in[j] = false, upd(j, c[j]); revert.clear();
      |                                                           ^~~~~~
#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...