Submission #1248086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248086		damoon	Monochrome Points (JOI20_monochrome)	C++20	0 / 100	1 ms	2376 KiB

monochrome

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

//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera

#define ll long long
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
#define f first
#define s second

#define lc 2*id
#define rc 2*id+1
#define mid (l+r)/2
#define all(x) x.begin(),x.end()

#define pb push_back
#define pp pop_back
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())
#define dig(x,d) ((x&(1ll<<d)) > 0)

string pr(int* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr( ll* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr( vector<ll> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr(pii* vv,int l,int r){for(int i=l;i<r;i++)cout<<"( "<<vv[i].f<<","<<vv[i].s<<" )    ";return "";}
string pr(vector<pii> vv){for(auto i:vv)cout<<"( "<<i.f<<","<<i.s<<" )    ";return "";}
string pr(bool* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i];return"";}
ostream& operator <<(ostream& out, pii x){out << "("<<x.f<<", "<<x.s<<") ";return out;}

random_device device;
default_random_engine rng(device());
#define randt(a,b) uniform_int_distribution<int64_t>(a,b)(rng)

const int L=5e5+10, mod=1e9+7;
const int inf=1e9+10;
int n;
bool c[L];
vector<int> av[2];
int a[L],cnt[2];

struct fen{
    int sum[L];
    fen(){
        fill(sum+1,sum+L,0);
    }
    void update(int ind,int x){
        for(int i=ind ; i<L ; i+=i&-i){
            sum[i] += x;
        }
    }
    int get(int ind){
        int ans = 0;
        for(int i=ind ; i>0 ; i-=i&-i){
            ans += sum[i];
        }
        return ans;
    }
}F;

int main(){
    //ofstream cout ("out.out");
    //ifstream cin ("in.in");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=2*n;i++){
        char inp;
        cin>>inp;
        c[i] = (inp == 'B');
    }
    for(int i=n+1;i<=2*n;i++){
        av[c[i]].pb(i-n);
    }

    for(int i=1;i<=n;i++){
        a[i] = av[!c[i]][cnt[c[i]]];
        cnt[c[i]]++;
    }

    int ans = 0;
    for(int i=1;i<=n;i++){
        ans += F.get(a[i]);
        F.update(a[i],1);
    }
    cout<<ans<<endl;
}

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