제출 #519748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519748		AngusWong	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	137 ms	29748 KiB

shoes

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

ll seg[800001];

ll query(ll id, ll l, ll r, ll x, ll y){
    if (x<=l && r<=y) return seg[id];
    if (l>y || r<x) return 0;
    ll mid=(l+r)/2;
    return query(id*2, l, mid, x, y)+query(id*2+1, mid+1, r, x, y);
}

void update(ll id, ll l, ll r, ll p){
    if (l==r){
        seg[id]++;
        return;
    }
    ll mid=(l+r)/2;
    if (p<=mid) update(id*2, l, mid, p);
    else update(id*2+1, mid+1, r, p);
    seg[id]=seg[id*2]+seg[id*2+1];
}

ll n, done[200001], ans=0;
set<ll> nxtl[100001], nxtr[100001];

ll count_swaps(vector<int> s){
    n=s.size();
    s.insert(s.begin(), 0);
    for (int i=0; i<=4*n; i++) seg[i]=0;
    for (int i=1; i<=n; i++){
        if (s[i]<0) nxtl[-s[i]].insert(i);
        else nxtr[s[i]].insert(i);
    }
    for (int i=1; i<=n; i++){
        if (done[i]) continue;
        if (s[i]<0){
            if (i%2==0 && !done[i+1] && s[i+1]==-s[i]){
                i++;
                continue;
            }
            int t=*(nxtr[-s[i]].lower_bound(i));
            nxtr[-s[i]].erase(t);
            done[t]=1;
            ans+=t-i-1-query(1, 1, n, i, t);
            update(1, 1, n, t);
        }else{
            int t=*nxtl[s[i]].lower_bound(i);
            nxtl[s[i]].erase(t);
            done[t]=1;
            ans+=t-i-query(1, 1, n, i, t);
            update(1, 1, n, t);
        }
    }
    return ans;
}

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