Submission #847651

#	Time	Username	Problem	Language	Result	Execution time	Memory
847651		manhlinh1501	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	4 ms	8796 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];

    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);
    }

    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;
            return;
        }

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

    i64 get(int pos) {
        int id = 1, l = 1, r = n;

        while(l < r) {
            int m = l + r >> 1;
            tree[rch] += tree[id];
            tree[lch] += tree[id];
            tree[id] = 0;

            if(pos > m) {
                id = rch;
                l = m + 1;

            } else {
                id = lch;
                r = m;
            }
        }
    }

    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);
    }

} 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:20:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         int m = l + r >> 1;
      |                 ~~^~~
shoes.cpp: In member function 'void IT::update(int, int, int, int, int, int)':
shoes.cpp:34:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int m = l + r >> 1;
      |                 ~~^~~
shoes.cpp: In member function 'i64 IT::get(int)':
shoes.cpp:46:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |             int m = l + r >> 1;
      |                     ~~^~~
shoes.cpp:60:5: warning: no return statement in function returning non-void [-Wreturn-type]
   60 |     }
      |     ^

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