Submission #1246770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246770		qwusha	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	213 ms	16852 KiB

shoes

#include "shoes.h"

#include <iostream>
#include <bits/stdc++.h>

#define fi first
#define se second
typedef long long ll;
using namespace std;

int inf = 1e9 + 7;


int n;

struct segtree {
    int sz = 1;
    vector<ll> tree;
    void init() {
        while (sz < n) {
            sz <<= 1;
        }
        tree.resize(sz * 2 - 1);
        build(0,0,sz);
    }
    void build(int v, int l, int r) {
        if (r - l == 1) {
            if (l < n) {
                tree[v] = 1;
            }
            return;
        }
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
        tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
    }
    void update(int ind, int newq) {
        upd(0,0,sz,ind,newq);
    }
    void upd(int v, int l, int r, int ind, int newq) {
        if (r - l == 1) {
            tree[v] = newq;
            return;
        }
        int m = (l + r) / 2;
        if (ind < m) {
            upd(v * 2 + 1, l, m, ind, newq);
        } else {
            upd(v * 2 + 2, m, r, ind, newq);
        }
        tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
    }
    ll answer(int lq, int rq) {
        return ans(0,0,sz,lq,rq);
    }
    ll ans(int v, int l, int r, int lq, int rq) {
        if (lq <= l && r <= rq) {
            return tree[v];
        }
        if (lq >= r || rq <= l) {
            return 0;
        }
        int m = (l + r) / 2;
        ll a1 = ans(v * 2 + 1, l, m, lq, rq),
        a2 = ans(v * 2 + 2, m, r, lq, rq);
        return a1 + a2;
    }
};


long long count_swaps(vector<int> s) {
    n = s.size();
    vector<int> pa(n);
    map<int, set<int>> mp;
    for (int i = 0; i < n; i++) {
        int val = s[i];
        if (mp.find(-val) == mp.end()) {
            mp[val].insert(i);
        } else {
            pa[*mp[-val].begin()] = i;
            mp[-val].erase(mp[-val].begin());
            if(mp[-val].empty()) {
                mp.erase(-val);
            }
        }
    }
    segtree tree;
    tree.init();
    ll res = 0;
    for (int i = 0; i < n; i++) {
        if (tree.answer(i, i + 1) == 0) {
            continue;
        }
        if (s[i] > 0) {
            res++;
        }
        res += tree.answer(i + 1, pa[i]);
        tree.update(pa[i], 0);
        tree.update(i, 0);
    }
    return res;
}

/*
signed main() {
    int n;
    cin >> n;
    vector<int> s(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        cin >> s[i];
    }
    int res = count_swaps(s);
    cout << res << endl;
}*/

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