Submission #847643

#	Time	Username	Problem	Language	Result	Execution time	Memory
847643		manhlinh1501	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	455 ms	155476 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

#define lch id << 1
#define rch id << 1 | 1

const int N = 2e5 + 5;

struct IT {
    int n;
    i64 tree[N << 2];
    i64 lazy[N << 2];

    void down(int id) {
        if(lazy[id] == 0)
            return;

        tree[lch] += lazy[id];
        lazy[lch] += lazy[id];

        tree[rch] += lazy[id];
        lazy[rch] += lazy[id];

        lazy[id] = 0;
    }

    void build(int id, int l, int r) {
        if(l == r) {
            tree[id] = r;
            return;
        }

        int m = l + r >> 1;
        build(lch, l, m);
        build(rch, m + 1, r);
        tree[id] = max(tree[lch], tree[rch]);
    }

    void update(int id, int l, int r, int u, int v, int k) {
        if(r<u or l>v)
            return;

        if(u <= l and r <= v) {
            tree[id] += k;
            lazy[id] += k;
            return;
        }

        int m = l + r >> 1;
        down(id);
        update(lch, l, m, u, v, k);
        update(rch, m + 1, r, u, v, k);
        tree[id] = max(tree[lch], tree[rch]);
    }

    i64 get(int id, int l, int r, int pos) {
        if(r<pos or l>pos)
            return 0;

        if(l == r)
            return tree[id];

        int m = l + r >> 1;
        down(id);
        return max(get(lch, l, m, pos), get(rch, m + 1, r, pos));
    }

    void create(int _n) {
        n = _n;
        build(1, 1, n);
    }

    void update(int l, int r, int k) {
        return update(1, 1, n, l, r, k);
    }

    int get(int pos) {
        return get(1, 1, n, pos);
    }
} ST;

i64 count_swaps(vector<int> a) {
    i64 ans = 0;
    map<int, deque<int>> res;
    int n = a.size();
    ST.create(n);

    for(int i = 0; i < n; i++) {
        if(res[-a[i]].empty())
            res[a[i]].emplace_back(i);

        else {
            int l = res[-a[i]].front() + 1;
            res[-a[i]].pop_front();
            int r = i+1;
            ans += ST.get(r) - ST.get(l) - (a[i] > 0);
            ST.update(l, r, 1);
        }
    }

    return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'void IT::build(int, int, int)':
shoes.cpp:34:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int m = l + r >> 1;
      |                 ~~^~~
shoes.cpp: In member function 'void IT::update(int, int, int, int, int, int)':
shoes.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int m = l + r >> 1;
      |                 ~~^~~
shoes.cpp: In member function 'i64 IT::get(int, int, int, int)':
shoes.cpp:64:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int m = l + r >> 1;
      |                 ~~^~~

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