Submission #1239444

#TimeUsernameProblemLanguageResultExecution timeMemory
1239444trantrungkeinMonochrome Points (JOI20_monochrome)C++20
0 / 100
1 ms1096 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 6; string s; int n,bi = 0, wi = 0, b[N],w[N],BIT[N]; void update(int id) { for(;id <= 2*n; id += (-id)&id) BIT[id] += 1; } int sum(int id) { int res = 0; for(;id > 0; id -= (-id)&id) res += BIT[id]; return res; } int get(int l, int r) { return (sum(r) - sum(l-1)); } int cal(int k) { vector<pair<int,int>> edge; memset(BIT,0,sizeof(BIT)); for(int i = 0; i < n; i++) { int c = min(w[i],b[(i+k)%n]) , d = max(w[i],b[(i+k)%n]); edge.push_back({c,d}); } sort(edge.begin(),edge.end()); int res = 0; for(auto [l,r] : edge) { //cout << l+1 <<' ' << r+1 << endl; res += get(l+1,r+1); update(r+1); } // cout << endl; //cout << res; return res; } int main() { cin >> n >> s; for(int i = 0; i < 2*n; i++) { if(s[i] == 'W') w[wi++] = i; else b[bi++] = i; } //cout << cal(0) << endl; int l = 0, r = n, ans = 0; while(l <= r) { int mid = (l+r)/2; int curr = cal(mid); int prev = 0; // cout << l <<' ' << r << ' ' << mid << endl; if(mid - 1 > 0) { prev = cal(mid-1); } ans = max(ans,curr); if(prev >= curr) { r = mid - 1; } else l = mid + 1; } cout << 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...