Submission #1263619

#TimeUsernameProblemLanguageResultExecution timeMemory
1263619ivopavMonochrome Points (JOI20_monochrome)C++20
35 / 100
2092 ms10464 KiB
#include <bits/stdc++.h> using namespace std; void upd(int ind,int val,vector<int>& tour,int ofs){ ind+=ofs; tour[ind]+=val; while (ind>1){ ind/=2; tour[ind]=tour[ind*2]+tour[ind*2+1]; } } int que(int l,int r,int l2,int r2,int ind,vector<int>& tour){ if (r<l2 || r2<l){ return 0; } if (l<=l2 && r2<=r){ return tour[ind]; } return que(l,r,l2,(l2+r2)/2,ind*2,tour)+que(l,r,(l2+r2)/2+1,r2,ind*2+1,tour); } int main(){ //ios_base::sync_with_stdio(false); //cin.tie(NULL); int n; string s; cin >> n >> s; int isp=0; int ofs=1; while (ofs<n*4){ ofs*=2; } for (int k=0;k<n*2;k++){ // cout << k << "\n"; int ind1=0; int ind2=k; vector<pair<int,int>> lis(n,pair<int,int>{}); for (int i=0;i<n;i++){ while (s[ind1]=='B'){ ind1++; } lis[i].first=ind1; while (s[ind2]=='W'){ ind2++; ind2%=n*2; } lis[i].second=ind2; if (lis[i].second<lis[i].first){ swap(lis[i].first,lis[i].second); } ind1++; ind1%=n*2; ind2++; ind2%=n*2; } sort(lis.begin(),lis.end()); int rje=0; vector<int> tour(ofs*2,0); for (int i=0;i<n;i++){ int a=lis[i].first; int b=lis[i].second; // cout << a << " " << b << "\n"; rje+=que(a,b,0,ofs-1,1,tour); // cout << rje << "\n"; upd(b,1,tour,ofs); // cout << "a\n"; } isp=max(isp,rje); // cout << rje << "\n"; } cout << isp << "\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...