Submission #1292211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292211		eri16	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1 ms	348 KiB

shoes

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

using ll = long long;

class ST{
  
private:
    vector <ll> tree;
 
    ll n;
 
    void build(vector <ll>& arr, ll node, ll start, ll end){
        
        if (start==end){tree[node]=arr[start];}
        else{
            ll mid=(start+end)/2;
            build(arr,2*node,start,mid);    
            build(arr,2*node+1,mid+1,end);
            tree[node]=tree[2*node]+tree[2*node+1];
        }
    }
    
    ll query(ll node, ll start, ll end, ll l, ll r){
        if (r<start || l>end){return 0;}
        else if(r>=end && l<=start){return tree[node];}
        else{
            ll mid=(start+end)/2;
            ll lseg=query(2*node,start,mid,l,r);
            ll rseg=query(2*node+1,mid+1,end,l,r);            
            return(lseg+rseg);
        }
    }
    
    void update(ll node, ll start, ll end, ll idx, ll val){
        
        ll mid=(start+end)/2;
        
        if (start==end){
            tree[node]=val;
        }
        
        else if(idx<=mid){
            update(2*node,start,mid,idx,val);
            
            tree[node]=tree[2*node]+tree[2*node+1];
            
        }
        
        else{
            update(2*node+1,mid+1,end,idx,val);
            
            tree[node]=tree[2*node]+tree[2*node+1];            
        }
        
    }
    
    
    
public:
 
    ST(vector<ll>& arr){
        n=arr.size();
        tree.resize(4*n);
        build(arr,1,0,n-1);
    }
    
    ll qu(ll l, ll r){
        return query(1,0,n-1,l,r);
    }
    
    void up(ll idx, ll val){
        update(1,0,n-1,idx,val);    
    }
};

long long count_swaps(vector <int> v){
    ll cnt=0,cur=0,n=v.size();    
    
    vector <ll> alive(n);
    
    for (int i=0; i<n; i++){alive[i]=1;}
    ST st(alive);
    
    map<ll,priority_queue<ll>> mp;
    
    for (ll i=0; i<n; i++){
        mp[v[i]].push(-i);
    }
    
    for (ll i=0; i<n; i++){
        if (i%2==0){
            cur=(v[i])*(-1);
        }    
        else{
            ll idx=mp[cur].top()*(-1);
            mp[cur].pop();
            mp[-cur].pop();
            st.up(idx,0);
            
            cnt+=st.qu(idx,i);
            
            if (v[i-1]>0){cnt++;}
        }
    }
    return cnt;
}

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