Submission #1263623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263623		ivopav	Monochrome Points (JOI20_monochrome)	C++20	4 / 100	1 ms	328 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;
    }
    vector<int> w={};
    vector<int> b={};
    for (int i=0;i<n*2;i++){
        if (s[i]=='W'){
            w.push_back(i);
        }
        else {
            b.push_back(i);
        }
    }
    for (int k=max(0,n/2-5);k<min(n,n/2+5);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++){
            
            lis[i].first=w[ind1];
            
            lis[i].second=b[ind2];
            if (lis[i].second<lis[i].first){
                swap(lis[i].first,lis[i].second);
            }
            ind1++;
            ind1%=n;
            ind2++;
            ind2%=n;
        }
        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 << k << " " << rje << "\n";
    }
    
    cout << isp << "\n";
    
}

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