Submission #1287190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287190		StefanSebez	Monochrome Points (JOI20_monochrome)	C++20	100 / 100	824 ms	8924 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=2e5+50,lg=18;
int n;string s;
vector<int>ids[2];
struct BIT{
    int T[2*N+1];
    void Update(int i,int x){for(;i<=2*N;i+=i&-i)T[i]+=x;}
    int Get(int i){int x=0;for(;i>=1;i-=i&-i)x+=T[i];return x;}
    int Get(int l,int r){return Get(r)-Get(l-1);}
}bt[2];
ll Calc(vector<int>p){
    ll cnt=0;
    int ev[2*n+1]={0};
    for(int i=0;i<n;i++){
        int l=ids[0][i],r=ids[1][p[i]];
        if(l>r)swap(l,r);
        ev[r+1]=l+1;
    }
    for(int i=1;i<=2*n;i++)if(ev[i]){
        cnt+=bt[0].Get(ev[i]-1)-bt[1].Get(ev[i]-1);
        bt[0].Update(ev[i],1);
        bt[1].Update(i,1);
    }
    for(int i=1;i<=2*n;i++)if(ev[i])bt[0].Update(ev[i],-1),bt[1].Update(i,-1);
    return cnt;
}
ll res,Val[N];
ll Calc(int j){
    if(Val[j]) return Val[j];
    vector<int>p={j};
    while(p.size()<n)p.pb((p.back()+1)%n);
    ll x=Calc(p);res=max(res,x);
    return Val[j]=x;
}
int main(){
    scanf("%i",&n);cin>>s;
    for(int i=0;i<2*n;i++){if(s[i]=='B') ids[0].pb(i);else ids[1].pb(i);}
    for(int i=0,e=1<<lg;e>=1;e>>=1){
        if(Calc(i)<Calc((i+1)%n)) i=(i+(e%n))%n;
        else if(Calc(i)<Calc((i-1+n)%n)) i=(i-(e%n)+n)%n;
    }
    printf("%lld\n",res);
    return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%i",&n);cin>>s;
      |     ~~~~~^~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 65 / 65