Submission #709722

#TimeUsernameProblemLanguageResultExecution timeMemory
709722AntekbMonochrome Points (JOI20_monochrome)C++17
35 / 100
1350 ms8884 KiB
#include<bits/stdc++.h> #define st first #define nd second #define eb emplace_back #define pb push_back #define mp make_pair #define pp pop_back #define all(x) x.begin(), x.end() using namespace std; using ll = long long; using pii = pair<int, int>; using vi = vector<int>; void debug(){cerr<<"\n";} template<typename H, typename... T> void debug(H h, T... t){cerr<<h;if(sizeof...(t))cerr<<", ";debug(t...);}; #define deb(x...) cerr<<#x<<" = ";debug(x); mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const int N=1<<19, INF=1e9+5; int tab[N+N]; void add(int v, int c){ for(v+=N; v; v>>=1)tab[v]+=c; } int sum(int l, int r){ int ans=0; for(l+=N,r+=N; l<r; l>>=1, r>>=1){ if(l&1)ans+=tab[l++]; if(r&1)ans+=tab[--r]; } return ans; } vi A, B; int n; ll solve(int a){ int wsk=n, wsk2=n; vector<pii> V(n); for(int i=0; i<a; i++){ //deb(wsk, wsk2); V[i]=mp(A[i], B[n-a+i]); } for(int i=a; i<n; i++){ V[i]=mp(A[i], B[i-a]); } for(pii &i:V)if(i.st>i.nd)swap(i.st, i.nd); sort(all(V)); int ans=0; for(int i=0; i<n; i++){ //deb(V[i]); //deb(V[i].st, V[i].nd); ans+=sum(V[i].st, V[i].nd); add(V[i].nd, 1); } for(int i=0; i<n; i++){ add(V[i].nd, -1); } //deb(ans); return ans; } ll res[N]; ll ans; ll getans(int t){ t%=n; if(res[t]==-1)res[t]=solve(t); ans=max(ans, res[t]); return res[t]; } int main(){ //ios_base::sync_with_stdio(0);cin.tie(0); cin>>n; string s; cin>>s; for(int i=0; i<n+n; i++){ if(s[i]=='B')A.pb(i); else B.pb(i); } for(int i=0; i<n; i++){ res[i]=-1ll; //deb(getans(i)); } if(n<=10){ for(int i=0;i<n; i++)getans(i); } else{ int k=n/8; for(int i=0; ;i+=k){ if(getans(i)<=getans(i+1) && getans(i+k)>getans(i+k+1)){ int l=i+1, r=i+k; while(l<r){ int m=(l+r)>>1; if(getans(m)<=getans(m+1))l=m+1; else r=m; } getans(r); break; } } } cout<<ans; }

Compilation message (stderr)

monochrome.cpp: In function 'll solve(int)':
monochrome.cpp:40:6: warning: unused variable 'wsk' [-Wunused-variable]
   40 |  int wsk=n, wsk2=n;
      |      ^~~
monochrome.cpp:40:13: warning: unused variable 'wsk2' [-Wunused-variable]
   40 |  int wsk=n, wsk2=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...