제출 #422663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422663		TryMax	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	67 ms	26384 KiB

shoes

#include "shoes.h"
#include "bits/stdc++.h"

using namespace std;

#define pb push_back
#define ll long long

const int N = 1e5 + 10;

int was[N], t[4 * N], w[4 * N];
vector<int> pos[2 * N];

void push(int u){
    w[2 * u + 1] += w[u];
    w[2 * u + 2] += w[u];
    t[2 * u + 1] += w[u];
    t[2 * u + 2] += w[u];
    w[u] = 0;
}

void upd(int u, int tl, int tr, int l, int r, int val){
    if(l <= tl && tr <= r){
        t[u] += val;
        w[u] += val;
        return;
    }
    push(u);
    int tm = (tl + tr) / 2;
    if(l <= tm)
        upd(2 * u + 1, tl, tm, l, r, val);
    if(r >= tm + 1)
        upd(2 * u + 2, tm + 1, tr, l, r, val);
}

int get_pos(int u, int tl, int tr, int pos){
    if(tl == tr)
        return t[u] + tl;
    push(u);
    int tm = (tl + tr) / 2;
    if(pos <= tm)
        return get_pos(2 * u + 1, tl, tm, pos);
    else
        return get_pos(2 * u + 2, tm + 1, tr, pos);
}

long long count_swaps(vector<int> s) {
	int n = s.size();
	ll ans = 0;
	for(int i = n - 1; i >= 0; --i)
        pos[N + s[i]].pb(i);
	for(int i = 0; i < n; ++i){
        if(was[i])
            continue;
        pos[N + s[i]].pop_back();
        if(s[i] < 0){
            int p = pos[N + -1 * s[i]].back();
            pos[N + -1 * s[i]].pop_back();
            was[p] = 1;
            ans += get_pos(0, 0, n, p) - get_pos(0, 0, n, i) - 1;
            upd(0, 0, n, i + 1, p - 1, 1);
        }else{
            int p = pos[N + -1 * s[i]].back();
            pos[N + -1 * s[i]].pop_back();
            was[p] = 1;
            ans += get_pos(0, 0, n, p) - get_pos(0, 0, n, i);
            upd(0, 0, n, i, p - 1, 1);
        }
//        cout << i << " " << ans << endl;
	}
	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