제출 #686686

#제출 시각아이디문제언어결과실행 시간메모리
686686JooDdaeRope (JOI17_rope)C++17
100 / 100
2106 ms85012 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define mid ((l+r) >> 1) const int INF = 1e9; int n, m, a[1001001], c[1001001]; vector<array<int, 2>> v[1001001]; int t[4004004]; void update(int id, int x, int node = 1, int l = 1, int r = n) { if(id < l || r < id) return; if(l == r) { t[node] += x; return; } update(id, x, node*2, l, mid), update(id, x, node*2+1, mid+1, r); t[node] = max(t[node*2], t[node*2+1]); } int main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) c[a[i]]++; for(int i=1;i<=m;i++) update(i, c[i]); for(int i=1;i<=n;i++) { int j = i; while(j < n && a[j+1] == a[j]) j++; v[a[i]].push_back({i, j}), i = j; } for(int i=1;i<=m;i++) { int ans = n-c[i]; update(i, -INF); { int p = 0, p2 = 0; for(auto [L, R] : v[i]) { // [0, 1] if(L != 1 && L%2 != 0) L--, p++, update(a[L], -1); if(R != n && R%2 != 1) R++, p++, update(a[R], -1); p2 += R-L+1; } ans = min(ans, p+n-p2-t[1]); for(auto [L, R] : v[i]) { // [0, 1] if(L != 1 && L%2 != 0) L--, update(a[L], 1); if(R != n && R%2 != 1) R++, update(a[R], 1); } } { int p = 0, p2 = 0; for(auto [L, R] : v[i]) { // [1, 0] if(L != 1 && L%2 != 1) L--, p++, update(a[L], -1); if(R != n && R%2 != 0) R++, p++, update(a[R], -1); p2 += R-L+1; } ans = min(ans, p+n-p2-t[1]); for(auto [L, R] : v[i]) { // [0, 1] if(L != 1 && L%2 != 1) L--, update(a[L], 1); if(R != n && R%2 != 0) R++, update(a[R], 1); } } update(i, INF); cout << ans << "\n"; } }
#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...