Submission #784998

#	Time	Username	Problem	Language	Result	Execution time	Memory
784998		HD1	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	507 ms	149260 KiB

shoes

//we are all lost trying to be someone.
#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=1e7+100;
const ll mod=1e9+7;
const ll inf=1e9;
ll tree[MAX], A[MAX];
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;
}
long long count_swaps(vector<int> c){
    for( ll i=0; i<sz(c) ; i++){
        M[c[i]].push(i);
    }
    ll ans=0;
    build_tree(1,0, sz(c));
    for(ll i = 0; i < sz(c); i++){
        if(sz(M[c[i]])>0){
            if(M[c[i]].front()!=i)continue;
            if(c[i]<0){
                ns=0;
                ll p=M[c[i]].front();
                query(1, 0,sz(c), p,p+1);
                M[c[i]].pop();
                ll a=ns;
                ns=0;
                ll q=M[c[i]*-1].front();
                ns=0;
                query(1, 0, sz(c), q, q+1);
                M[c[i]*-1].pop();
                ll b=ns;
                ans+=b-a-1;
                update(1,0, sz(c),p,q);
            }
            else{
                ns=0;
                ll p=M[c[i]].front();
                query(1, 0,sz(c), p,p+1);
                M[c[i]].pop();
                ll a=ns;
                ns=0;
                ll q=M[c[i]*-1].front();
                ns=0;
                query(1, 0, sz(c), q, q+1);
                M[c[i]*-1].pop();
                ll b=ns;
                ans+=b-a;
                update(1,0, sz(c),p,q);
            }
        }
    }
    return ans;
}

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