제출 #1307649

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307649		hectormedrano	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	157 ms	148768 KiB

shoes

#include <cstdio>
#include <cassert>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> st(8e5+5);

void update(ll l, ll r, ll ind, ll pos){
    if(l == r){st[ind]++; return;}
    ll m = (l+r)/2;
    if(pos<=m){
        update(l, m, 2*ind, pos);
    } else {
        update(m+1, r, 2*ind+1, pos);
    }
    st[ind] = st[2*ind] + st[2*ind+1];
}

ll query(ll l, ll r, ll ind, ll ql, ll qr){
    if(r<ql or qr<l){return 0;}
    if(ql<=l and r<=qr){return st[ind];}
    ll m = (l+r)/2;
    return query(l, m, 2*ind, ql, qr) + query(m+1, r, 2*ind+1, ql, qr);
}

ll count_swaps(vector<int> s) {
    for(ll i=0;i<8e5+5;i++){st[i]=0;}
    ll inv = 0;
    ll n = s.size();
    n = n/2;
    vector<pair<ll, ll>> a;
    vector<bool> u(2*n, false);
    vector<queue<ll>> q(2*n+1);
    for(ll i=0;i<2*n;i++){
        q[n+s[i]].push(i);
    }
    for(ll i=0;i<2*n;i++){
        if(!(u[i])){
            ll pos = q[n-s[i]].front();
            if(s[i]<0){
                a.push_back({s[i], i});
                a.push_back({-s[i], pos});
            } else {
                a.push_back({s[i], pos});
                a.push_back({-s[i], i});
            }
            u[pos] = true;
            u[i] = true;
            q[n-s[i]].pop();
            q[n+s[i]].pop();
        }
    }
    //for(pair<ll, ll> p : a){cout<<p.first<<" "<<p.second<<endl;}
    for(ll i=0;i<2*n;i++){
        inv += query(0, 2*n-1, 1, a[i].second, 2*n-1);
        update(0, 2*n-1, 1, a[i].second);
    }
	return inv;
}

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