Submission #796829

#	Time	Username	Problem	Language	Result	Execution time	Memory
796829		HD1	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	274 ms	298520 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 int ll;
    typedef long double ld;
    const ll MAX=1e5+100;
    const ll mod=1e9+7;
    const ll inf=1e9;
    int tree[MAX*4], A[MAX*4];
    int n=0;
    map<int,queue<int>>M;
    void build_tree(int id, int l, int r){
      if(r-l==1){
        tree[id]=l;
        return;
      }
      int mid=(l+r)/2;
      build_tree(id*2, l, mid);
      build_tree(id*2+1, mid, r);
      return;
    }
    void update(int id, int l, int r, int L, int R){
        if(l>=R or r<=L) return;
        if(l>=L and r<=R){
            tree[id]++;
            return;
        }
        int mid=(l+r)/2;
        update(id*2, l, mid, L, R);
        update(id*2+1, mid, r, L, R);
        return;
    }
    int ns=0;
    void query(int id, int l, int r, int L, int 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);
        }
        long long 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;
    }
    /*int main(){
        ll a;
        cin>>n;
        vector<ll> k;
        for(ll i=0; i<n; i++){
            cin>>a;
            k.push_back(a);
        }
        cout<<count_swaps(k)<<'\n';
    }*/

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