oj.uz

Submission #893675

# Submission time Handle Problem Language Result Execution time Memory
893675 2023-12-27T09:00:59 Z Darren0724 Monochrome Points (JOI20_monochrome) C++17
0 / 100
 2 ms 3632 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
#define x first
#define y second
const int N=400005;
const int INF=1e18;
const int mod=924844033;
struct BIT{
    vector<int> v=vector<int>(N);
    void add(int p,int t){
        for(int i=p;i<N;i+=i&(-i)){
            v[i]+=t;
        }
    }
    int ask(int p){
        int ans=0;
        for(int i=p;i>0;i-=i&(-i)){
            ans+=v[i];
        }
        return ans;
    }
};
int32_t main() {
    LCBorz;
    int n;cin>>n;
    string s;cin>>s;
    vector<int> a,b;
    for(int i=0;i<n<<1;i++){
        if(s[i]=='W'){
            a.push_back(i+1);
        }
        else{
            b.push_back(i+1);
        }
    }    
    auto solve=[&](int k)->int {
        vector<pair<int,int>> v(n);
        BIT bit;
        for(int i=0;i<n;i++){
            v[i]=make_pair(a[i],b[(i+k)%n]);
            if(v[i].x>v[i].y){
                swap(v[i].x,v[i].y);
            }
            bit.add(v[i].x,1);
            bit.add(v[i].y,-1);
        }
        int ans=0;
        sort(all(v));
        for(int i=0;i<n;i++){
            ans+=bit.ask(v[i].y-1)-bit.ask(v[i].x);
            bit.add(v[i].x,-1);
            bit.add(v[i].y,2);
        }
        return ans;
    };
    int ans=0;
    int l=0,r=(n+1)/2;
    while(r-l>1){
        int m=(l+r)>>1;
        if(solve(m)>solve(m+1)){
            r=m;
        }
        else{
            l=m;
        }
    }
    ans=max(solve(l),solve(l+1))/2;
    cout<<ans<<endl;

    return 0;
}

Subtask #1
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3616 KB Output is correct
2 Correct 2 ms 3632 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Incorrect 2 ms 3576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3616 KB Output is correct
2 Correct 2 ms 3632 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Incorrect 2 ms 3576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3616 KB Output is correct
2 Correct 2 ms 3632 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Incorrect 2 ms 3576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3616 KB Output is correct
2 Correct 2 ms 3632 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Incorrect 2 ms 3576 KB Output isn't correct
5 Halted 0 ms 0 KB -