Submission #1311438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311438		aleksandre	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	391 ms	149936 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> segtree;
void build(int node, int l, int r) {
    if (l == r) {
        segtree[node] = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(node*2, l, mid);
    build(node*2+1, mid+1, r);
    segtree[node] = segtree[node*2] + segtree[node*2+1];
}
void update(int node, int l, int r, int pos, int val) {
    if (l == r) {
        segtree[node] = val;
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(node*2, l, mid, pos, val);
    else update(node*2+1, mid+1, r, pos, val);
    segtree[node] = segtree[node*2] + segtree[node*2+1];
}
int query(int node, int l, int r, int L, int R) {
    if (R < l || L > r) return 0;
    if (L <= l && r <= R) return segtree[node];
    int mid = (l + r) / 2;
    return query(node*2, l, mid, L, R) +
           query(node*2+1, mid+1, r, L, R);
}
long long count_swaps(vector<int> s) {
    int n = s.size();
    N = n;
    segtree.assign(4*n, 0);
    long long ans = 0;
    map<int, queue<int>> pos;
    for (int i = 0; i < n; i++) {
        pos[s[i]].push(i);
    }
    build(1, 0, n-1);
    vector<int> used(n, 0);
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        int par = pos[-s[i]].front();
        pos[-s[i]].pop();
        pos[s[i]].pop();
        long long bet;
        if (i < par) {
            bet = query(1, 0, n-1, i+1, par-1);
        } else {
            bet = query(1, 0, n-1, par+1, i-1);
        }
        if (s[i] < 0) ans += bet;
        else ans += bet + 1;
        used[i] = used[par] = 1;
        update(1, 0, n-1, i, 0);
        update(1, 0, n-1, par, 0);
    }
    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