Submission #1311430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311430		aleksandre	Arranging Shoes (IOI19_shoes)	C++20	15 / 100	333 ms	149932 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
    int n;
    vector<int> t;
    SegmentTree(int n) : n(n), t(4*n, 0) {}
    void build(int node, int l, int r) {
        if (l == r) {
            t[node] = 1; 
            return;
        }
        int mid = (l + r) / 2;
        build(node*2, l, mid);
        build(node*2+1, mid+1, r);
        t[node] = t[node*2] + t[node*2+1];
    }
    void update(int node, int l, int r, int pos, int val) {
        if (l == r) {
            t[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);
        t[node] = t[node*2] + t[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 t[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();
    long long ans = 0;
    map<int, queue<int>> pos;
    for (int i = 0; i < n; i++) {
        pos[s[i]].push(i);
    }
    SegmentTree seg(n);
    seg.build(1, 0, n-1);
    vector<int> used(n, 0);
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        int partner = pos[-s[i]].front();
        pos[-s[i]].pop();
        pos[s[i]].pop();
        if (i < partner) {
            ans += seg.query(1, 0, n-1, i+1, partner-1);
        } else {
            ans += seg.query(1, 0, n-1, partner+1, i-1);
        }
        used[i] = used[partner] = 1;
        seg.update(1, 0, n-1, i, 0);
        seg.update(1, 0, n-1, partner, 0);
    }
    return ans;
}

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