Submission #837548

#TimeUsernameProblemLanguageResultExecution timeMemory
837548LiudasRope (JOI17_rope)C++17
80 / 100
597 ms191148 KiB
#include <bits/stdc++.h> using namespace std; class segment_tree{ public: int tree[50000] = {0}; int N = 25000; void update(int head, int l, int r, int pos, int val){ if(r - l == 1){ tree[head] += val; return; } int mid = (l + r) / 2; if(pos < mid){ update(head * 2 + 1, l, mid, pos, val); } else{ update(head *2 + 2, mid, r, pos, val); } tree[head] = max(tree[head * 2 + 2], tree[head * 2 + 1]); } void update(int pos, int val){ update(0, 0, N, pos, val); } }; int arr[1000050]; int main(){ int N, M; cin >> N >> M; for(int i = 0; i < N; i ++){ cin >> arr[i]; arr[i]--; } segment_tree tree; vector<vector<vector<int>>> brr(M + 5, vector<vector<int>>(2)); vector<int> counts(M + 5); for(int i = 0; i < N; i ++){ for(int j = 0; j < 2; j ++){ int pi = i + 1 - (i + j) % 2 * 2; if(pi > -1 && pi < N && arr[pi] != arr[i]){ brr[arr[i]][j].push_back(arr[pi]); } } counts[arr[i]] ++; tree.update(arr[i], 1); } for(int i = 0; i < M; i ++){ tree.update(i, -counts[i]); int ans = N; for(int j = 0; j < 2; j ++){ for(int &k : brr[i][j])tree.update(k, -1); ans = min(ans, N-tree.tree[0]-counts[i]); for(int &k : brr[i][j])tree.update(k, 1); } tree.update(i, counts[i]); cout << ans << endl; } }
#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...