Submission #1263619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263619		ivopav	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	2092 ms	10464 KiB

monochrome

#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";
    
}

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