Submission #891431

#	Time	Username	Problem	Language	Result	Execution time	Memory
891431		Sir_Ahmed_Imran	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	216 ms	274704 KiB

shoes

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define N 200000
int seg[4*N];
void add(int x,int v=1,int s=0,int e=N){
    seg[v]++;
    if(e-s==1) return;
    int mid=(s+e)/2;
    if(x<mid) add(x,2*v,s,mid);
    else add(x,2*v+1,mid,e);
}
int get(int l,int r,int v=1,int s=0,int e=N){
    if(r<=s || e<=l || r<=l) return 0;
    if(l<=s && e<=r) return seg[v];
    int mid=(s+e)/2;
    return get(l,r,2*v,s,mid)+get(l,r,2*v+1,mid,e);
}
queue<int> l[N];
queue<int> r[N];
ll count_swaps(vector<int> v){
    ll o=0;
    int n=v.size()/2;
    for(int i=0;i<2*n;i++){
        if(v[i]<0){
            if(r[-v[i]].empty()){
                add(i);
                l[-v[i]].push(i);
            }
            else{
                o+=get(r[-v[i]].front(),i);
                add(r[-v[i]].front());
                r[-v[i]].pop();
            }
        }
        else{
            if(l[v[i]].empty()){
                add(i);
                r[v[i]].push(i);
            }
            else{
                o+=get(l[v[i]].front(),i)-1;
                add(l[v[i]].front());
                l[v[i]].pop();
            }
        }
    }
    return o;
}

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