Submission #1040785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040785		Andrey	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	38 ms	9648 KiB

monochrome

#include<bits/stdc++.h>
using namespace std;

vector<long long> pr(200010);
long long n;

void dude(long long l, long long r, long long x, long long c, bool yeah) {
    if(r < l) {
        return;
    }
    if(yeah) {
        l-=x;
        r-=x;
    }
    else {
        l = x-l;
        r = x-r;
        swap(l,r);
    }
    if(l < 0) {
        l+=n;
    }
    if(r < 0) {
        r+=n;
    }
    if(l <= r) {
        pr[l]+=c;
        pr[r+1]-=c;
    }
    else {
        pr[l]+=c;
        pr[n]-=c;
        pr[0]+=c;
        pr[r+1]-=c;
    }
}

void calc(bool yeah, vector<long long> p, vector<long long> q) {
    for(long long i = 1; i <= n; i++) {
        long long c = p[i];
        long long l = 0,r = n,p1,p2;
        while(l < r) {
            long long mid = (l+r+1)/2;
            if(q[mid] > c) {
                r = mid-1;
            }
            else {
                l = mid;
            }
        }
        p1 = l;
        if(c <= n) {
            l = 0;
            r = n;
            while(l < r) {
                long long mid = (l+r+1)/2;
                if(q[mid] > c+n) {
                    r = mid-1;
                }
                else {
                    l = mid;
                }
            }
            p2 = l;
            dude(1,p1,i,c,yeah);
            dude(p1+1,p2,i,-c,yeah);
            if(yeah) {
                dude(p2+1,n,i,2*n+c,yeah);
            }
            else {
                dude(p2+1,n,i,c,yeah);
            }
        }
        else {
            l = 0;
            r = n;
            while(l < r) {
                long long mid = (l+r+1)/2;
                if(q[mid] < c-n) {
                    l = mid;
                }
                else {
                    r = mid-1;
                }
            }
            p2 = l;
            if(yeah) {
                dude(1,p2,i,2*n-c,yeah);
            }
            else {
                dude(1,p2,i,-c,yeah);
            }
            dude(p2+1,p1,i,c,yeah);
            dude(p1+1,n,i,-c,yeah);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    string s;
    cin >> s;
    vector<long long> p(1);
    vector<long long> q(1);
    for(long long i = 0; i < 2*n; i++) {
        if(s[i] == 'B') {
            p.push_back(i+1);
        }
        else {
            q.push_back(i+1);
        }
    }
    p.push_back(LLONG_MAX);
    q.push_back(LLONG_MAX);
    calc(1,p,q);
    calc(0,q,p);
    long long c = 0,ans = 0;
    for(long long i = 0; i < n; i++) {
        c+=pr[i];
        ans = max(ans,(c-n)/2);
    }
    cout << ans;
    return 0;
}

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