Submission #366298

#	Time	Username	Problem	Language	Result	Execution time	Memory
366298		farhan132	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	524 ms	8812 KiB

monochrome

/***Farhan132***/

#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vi;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
 
#define ff first
#define ss second
#define pb push_back
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define PI 3.14159265359
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)
#define clean fflush(stdout)

const ll mod =  (ll)1e9 + 7;
const ll maxn = (ll)4e5 + 5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
//const ll INF = 1e18;
 
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};

/**
===========
Lost + something = something
Same + Same = Lost
i + j = i ^ j
===========
**/

int ft[maxn];
void update(int p, int x) {
  for(; p < maxn; p += p & -p)
    ft[p] += x;
}
int sum(int l, int r) {
  int ret = 0;
  for(--l; l > 0; l -= l & -l) ret -= ft[l];
  for(; r > 0; r -= r & -r) ret += ft[r];
  return ret;
}

ll n;
vector < ll > v[3];
ll a[maxn] , b[2*maxn];

long long f(ll x){
    long long ans = 0;
    ll seg [2*n + 5];
    for(ll i = 0; i < n; i++){
        ll X = v[0][i];
        ll Y = v[1][(i+x)%n];
        if(Y < X) swap(X,Y);
        seg[X] = Y;
        seg[Y] = X;
    }
    ll cnt = 0;
    for(ll i = 1; i <= 2*n; i++) ft[i] = 0;
    for(ll i = 1; i <= 2*n; i++) b[i] = 0;
    for(ll i = 1; i <= 2*n; i++){
        ll X = i;
        ll Y = seg[i];
        if(b[X]){
            update(X , 0);
            continue;
        }
        b[Y] = 1;
        ll k = sum(X, Y);
        ans += k;
        update(Y, 1);
    }
    return ans;
}

void solve(){

    cin >> n;
    for(ll i = 1; i <= 2*n; i++){
        char c;
        cin >> c;
        if(c == 'B') a[i] = 1;
        else a[i] = 0;
        v[a[i]].pb(i);
    }
    long long ans = 0;
    ll lo = 0, hg = n-1;
    while(lo <= hg){
        ll mid = (lo + hg)/2;
        long long x1 = f(mid) , x2 = f(mid+1);
        if(x1 < x2) ans = max(ans , x2) , lo = mid+1;
        else ans = max(ans , x1) , hg = mid-1; 
    }
    cout << ans;

    return;    
}

 
int main() {
    
    
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else 
     //   freopen("cbarn2.in", "r", stdin);
     //   freopen("cbarn2.out", "w", stdout);
     ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    #endif
    //cout << fixed << setprecision(10);
   // work(maxn);
    //  mem(b,0);
    ll T;
    T=1;
    //cin >> T; 
    //scanf("%lld",&T);
   // ll CT = 0;
    //work();
    while(T--){
        //cout << "Case " << ++CT <<": " ;
        //printf("Case %lld: ",++CT);
        solve();
    }
 
    return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'long long int f(ll)':
monochrome.cpp:83:8: warning: unused variable 'cnt' [-Wunused-variable]
   83 |     ll cnt = 0;
      |        ^~~

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