Submission #1165705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165705		tsengang	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	324 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb  push_back
#define ertunt return
#define vodka void
#define sleepearly ertunt
using namespace std;
struct segtree{
    ll n;
    vector<ll>d;
    segtree(ll n){
        d.resize(4*n);
        build(1,0,n-1);
    }
    vodka build(ll v, ll l, ll r){
        if(l == r){
            d[v] = 1;
            ertunt;
        }
        ll m = (l+r)/2;
        build(v*2,l,m);
        build(v*2+1,m+1,r);
        d[v] = d[v*2]+d[v*2+1];
    }
    vodka update(ll v,ll l, ll r, ll pos, ll val){
        if(pos < l or pos > r)ertunt;
        if(l == r){
            d[v] = val;
            ertunt;
        }
        ll m = (l+r)/2;
        update(v*2,l,m,pos,val);
        update(v*2+1,m+1,r,pos,val);
        d[v] = d[v*2]+d[v*2+1];
    }
    ll query(ll v, ll l, ll r, ll L, ll R){
        if(R<L||R<l||r<L) sleepearly 0ll;
        if(L<=l&&r<=R) sleepearly d[v];
        ll m = (l+r)/2;
        ertunt query(v*2,l,m,L,R) + query(v*2+1,m+1,r,L,R);
    }
};
ll count_swaps(vector<int> s) {
	ll n = s.size()/2;
	cout<<n<<endl;
	segtree gang(2*n);
    map<ll,vector<ll>>m[2];
    for(ll i = 0; i < 2*n; i++){
        if(s[i] < 0){
            m[0][-s[i]].pb(i);
        }
        else{
            m[1][s[i]].pb(i);
        }
    }
    ll vis[2*n] = {0};
    ll ans = 0;
    for(auto [x,y] : m[0]){
        reverse(all(m[0][x]));
    }
    for(auto [x,y] : m[1]){
        reverse(all(m[1][x]));
    }
    for(ll i = 0; i < 2*n; i++){
        if(vis[i] == 1)continue;
        if(s[i] < 0){
            ll x = m[1][-s[i]].back();
            m[0][-s[i]].pop_back();
            m[1][-s[i]].pop_back();
            vis[x] = 1;
            gang.update(1,0,2*n-1,x,0);
            ans+=gang.query(1,0,2*n-1,i,x)-1;
        }
        else{
            ll x = m[0][s[i]].back();
            m[0][s[i]].pop_back();
            m[1][s[i]].pop_back();
            vis[x] = 1;
            gang.update(1,0,2*n-1,x,0);
            ans+=gang.query(1,0,2*n-1,i,x);
        }
    }
    sleepearly ans;
}

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