Submission #796831

#	Time	Username	Problem	Language	Result	Execution time	Memory
796831		HD1	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	570 ms	151256 KiB

shoes

    //we are all lost trying to be someone.
    #include "shoes.h"
    #include <bits/stdc++.h>
    #define fastio ios_base::sync_with_stdio(0); cin.tie(0);
    #define sz(x) ll(x.size())
    #define reve(x) reverse(x.begin(),x.end())
    #define ff first
    #define ss second
    #define pb push_back
    using namespace std;
    typedef long long  ll;
    typedef long double ld;
    const ll MAX=1e6+100;
    const ll mod=1e9+7;
    const ll inf=1e9;
    ll tree[MAX], A[MAX];
    ll n=0;
    map<ll,queue<ll>>M;
    void build_tree(ll id, ll l, ll r){
      if(r-l==1){
        tree[id]=l;
        return;
      }
      ll mid=(l+r)/2;
      build_tree(id*2, l, mid);
      build_tree(id*2+1, mid, r);
      return;
    }
    void update(ll id, ll l, ll r, ll L, ll R){
        if(l>=R or r<=L) return;
        if(l>=L and r<=R){
            tree[id]++;
            return;
        }
        ll mid=(l+r)/2;
        update(id*2, l, mid, L, R);
        update(id*2+1, mid, r, L, R);
        return;
    }
    ll ns=0;
    void query(ll id, ll l, ll r, ll L, ll R){
        if(l>=R or r<=L) return;
        ns+=tree[id];
        if(l>=L and r<=R){
            return;
        }
        ll mid=(l+r)/2;
        query(id*2, l, mid, L, R);
        query(id*2+1, mid, r, L, R);
        return;
    }
    ll aport(ll p, ll q, ll x, ll y){
        ns=0;
        query(1, 0,n, p,p+1);
        M[y].pop();
        ll a=ns;
        ns=0;
        query(1, 0, n, q, q+1);
        M[y*-1].pop();
        ll b=ns;
        if(x==1)update(1,0, n,p+1,q);
        else update(1,0, n,p,q);
        return b-a;
    }
    long long count_swaps(vector<int> c){
        n=sz(c);
        for( ll i=0; i<n ; i++){
            M[c[i]].push(i);
        }
        ll ans=0;
        build_tree(1,0, n);
        for(ll i = 0; i < n; i++){
            if(sz(M[c[i]])>0){
                if(M[c[i]].front()!=i)continue;
                ll p=M[c[i]].front();
                ll q=M[c[i]*-1].front();
                if(c[i]<0){
                    ans+=aport(p,q,1, c[i])-1;
                }
                else{
                    ans+=aport(p,q,0,c[i]);
                }
            }
        }
        return ans;
    }

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15