Submission #1236399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236399		mariza	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	165 ms	152252 KiB

shoes

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

typedef long long ll;
#define MID ((l+r)/2)

struct node{
    ll val;
    node *L, *R;

    void init(ll l, ll r){
        val=0;

        if(l!=r){
            L=new node;
            L->init(l,MID);

            R=new node;
            R->init(MID+1,r);
        }
    }

    void upd(ll l, ll r, ll i){
        if(l==i && i==r){
            val=1;
        }
        else if(l<=i && i<=r){
            val++;
            L->upd(l,MID,i);
            R->upd(MID+1,r,i);
        }
    }

    ll ans(ll l, ll r, ll tl, ll tr){
        if(tl<=l && r<=tr) return val;
        else if(r<tl || tr<l) return 0;
        else return L->ans(l,MID,tl,tr) + R->ans(MID+1,r,tl,tr);
    }
};

long long count_swaps(vector<int> s){
    ll n=s.size()/2;

    queue<ll> l[n+1], r[n+1];
    ll c=0;
    for(ll i=0; i<2*n; i++){
        if(s[i]<0){
            l[-s[i]].push(2*c);
            r[-s[i]].push(2*c+1);
            // cout<<-s[i]<<" "<<2*i<<endl;
            c++;
        }
    }
    // cout<<"ok1"<<endl;

    vector<ll> s2;
    ll pos[2*n];
    for(ll i=0; i<2*n; i++){
        if(s[i]<0){
            s2.push_back(l[-s[i]].front());
            pos[l[-s[i]].front()]=s2.size()-1;
            l[-s[i]].pop();
        }
        else{
            s2.push_back(r[s[i]].front());
            pos[r[s[i]].front()]=s2.size()-1;
            r[s[i]].pop();
        }
    }
    // cout<<"ok2"<<endl;

    node seg;
    seg.init(0,2*n-1);
    // cout<<"ok3"<<endl;

    ll ans=0;
    for(ll i=2*n-1; i>=0; i--){
        // cout<<i<<endl;
        ans+=seg.ans(0,2*n-1,0,pos[i]);
        seg.upd(0,2*n-1,pos[i]);
        // cout<<i<<endl;
    }
    
    return ans;
}

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