Submission #1001146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001146		shmax	Jousting tournament (IOI12_tournament)	C++17	0 / 100	916 ms	9436 KiB

tournament

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")

using namespace std;
using namespace __gnu_pbds;
#define int long long
#define float long double
#define elif else if
#define endl "\n"
#define mod 1000000007
#define pi acos(-1)
#define eps 0.000000001
#define inf 1000'000'000'000'000'000LL
#define FIXED(a) cout << fixed << setprecision(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define time_init auto start = std::chrono::high_resolution_clock::now()
#define time_report                                       \
    auto end = std::chrono::high_resolution_clock::now(); \
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl
#define debug(x) \
    { cerr << #x << " = " << x << endl; }
#define len(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) | (1LL << (i)))
#define clear_bit(x, i) ((x) & (~(1LL << (i))))
#define toggle_bit(x, i) ((x) ^ (1LL << (i)))
#define low_bit(x) ((x) & (-(x)))
#define count_bit(x) __builtin_popcountll(x)
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))
#define mp make_pair
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxelpos(x) (max_element(all(x)) - x.begin())
#define minelpos(x) (min_element(all(x)) - x.begin())
#define sum(x) (accumulate(all(x), 0LL))
#define product(x) (accumulate(all(x), 1LL, multiplies<int>()))
#define gcd __gcd
#define lcm(a, b) ((a) / gcd(a, b) * (b))
#define rev(x) (reverse(all(x)))
#define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end()))
#define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend()))
#define is_sorted(x) (is_sorted_until(all(x)) == x.end())
#define is_even(x) (((x) &1) == 0)
#define is_odd(x) (((x) &1) == 1)
#define pow2(x) (1LL << (x))

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using matrix = vector<vector<T>>;
template<typename T>
using graph = vector<vector<T>>;
using hashmap = gp_hash_table<int, int, custom_hash>;

template<typename T>
vector<T> vect(int n, T val) {
    return vector<T>(n, val);
}

template<typename T>
vector<vector<T>> vect(int n, int m, T val) {
    return vector<vector<T>>(n, vector<T>(m, val));
}

template<typename T>
vector<vector<vector<T>>> vect(int n, int m, int k, T val) {
    return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val)));
}

template<typename T>
vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) {
    return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val))));
}

template<typename T>
matrix<T> new_matrix(int n, int m, T val) {
    return matrix<T>(n, vector<T>(m, val));
}

template<typename T>
graph<T> new_graph(int n) {
    return graph<T>(n);
}

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;

template<typename T>
using vec = vector<T>;

using pII = pair<int, int>;
template<typename T>
using enumerated = pair<T, int>;


template<typename T, typename P>
struct SegmentTree {
private:
    function<T(const T &, const T &)> comb;
    function<void(T &, const P, int, int)> apply_push;
    function<void(P &, const P &)> merge_push;
    function<pair<P, P>(const P &, int l, int r, int pos)> split_push;
    size_t n;
    vec<T> tree;
    vec<optional<P>> pushes;

    void push(int v, int tl, int tr) {
        if (!pushes[v].has_value())
            return;
        if (tl != tr) {
            int tm = (tl + tr) / 2;
            auto [l, r] = split_push(pushes[v].value(), tl, tr, tm);
            apply_push(tree[2 * v], l, tl, tm);
            apply_push(tree[2 * v + 1], r, tm + 1, tr);
            if (pushes[2 * v].has_value())
                merge_push(pushes[2 * v].value(), l);
            else
                pushes[2 * v] = l;
            if (pushes[2 * v + 1].has_value())
                merge_push(pushes[2 * v + 1].value(), r);
            else
                pushes[2 * v + 1] = r;
        }

        pushes[v] = nullopt;
    }

    void build(int v, int tl, int tr, const vec<T> &a) {
        if (tl == tr) {
            tree[v] = a[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm, a);
        build(2 * v + 1, tm + 1, tr, a);
        tree[v] = comb(tree[2 * v], tree[2 * v + 1]);
    }

    T get(int v, int tl, int tr, int l, int r) {
        if (l > r)
            return T();
        if (l == tl && r == tr)
            return tree[v];
        push(v, tl, tr);
        int tm = (tl + tr) / 2;
        if (r <= tm)
            return get(2 * v, tl, tm, l, r);
        if (l > tm)
            return get(2 * v + 1, tm + 1, tr, l, r);

        return comb(get(2 * v, tl, tm, l, tm), get(2 * v + 1, tm + 1, tr, tm + 1, r));
    }

    void update(int v, int tl, int tr, int l, int r, const P &val) {
        if (l > r)
            return;
        if (l == tl && r == tr) {
            apply_push(tree[v], val, l, r);
            if (pushes[v].has_value())
                merge_push(pushes[v].value(), val);
            else
                pushes[v] = val;
            return;
        }
        push(v, tl, tr);
        int tm = (tl + tr) / 2;
        if (r <= tm)
            update(2 * v, tl, tm, l, r, val);
        elif (l > tm)update(2 * v + 1, tm + 1, tr, l, r, val);
        else {
            auto [lval, rval] = split_push(val, l, r, tm);
            update(2 * v, tl, tm, l, tm, lval);
            update(2 * v + 1, tm + 1, tr, tm + 1, r, rval);
        }
        tree[v] = comb(tree[2 * v], tree[2 * v + 1]);
    }

public:

    SegmentTree(const function<T(const T &, const T &)> &comb,
                const function<void(T &, const P, int, int)> &apply_push,
                const function<void(P &, const P &)> &merge_push,
                const function<pair<P, P>(const P &, int l, int r, int pos)> &split_push) :
            comb(comb), apply_push(apply_push), merge_push(merge_push), split_push(split_push) {

    }


    T get(int l, int r) {
        return get(1, 0, n - 1, l, r);
    }

    T operator[](int i) {
        return get(i, i);
    }

    T operator()(int l, int r) {
        return get(l, r);
    }

    void update(int l, int r, const P &val) {
        update(1, 0, n - 1, l, r, val);
    }

    void init(int _n, const vec<T> &a) {
        this->n = _n;
        tree.clear();
        pushes.clear();
        tree.resize(4 * n);
        pushes.resize(4 * n);
        build(1, 0, n - 1, a);
    }

    void init(const vec<T> &a) {
        init(len(a), a);
    }

    void init(int _n, const T &val) {
        init(_n, vect<T>(_n, val));
    }

    void reset() {
        fill(all(tree), T());
        fill(all(pushes), nullopt);
    }

};

using Push = int;
using Vertex = int;
auto split_push = [](const Push &p, int tl, int tr, int pos) {
    return mp(p, p);
};

auto merge_push = [](Push &p, const Push &q) {
    p = q;
};

auto apply_push1 = [](Vertex &x, const Push &p, int l, int r) {
    x += p * (r - l + 1);
};
auto comb = [](const Vertex &x, const Vertex &y) {
    return x + y;
};

SegmentTree<Vertex, Push> st1(comb, apply_push1, merge_push, split_push);


struct PrefixSum {
    int n;
    vector<int> pref;

    explicit PrefixSum(const vector<int> &a) {
        n = len(a);
        pref = vect(n, 0LL);
        pref[0] = a[0];
        for (int i = 1; i < n; i++) {
            pref[i] = pref[i - 1] + a[i];
        }
    }

    int get(int l, int r) {
        if (l == 0) {
            return pref[r];
        } else {
            return pref[r] - pref[l - 1];
        }
    }
};

template<typename T>
struct range_fenvik {
private:
    vector<T> diff_tree;
    vector<T> diff_mul_tree;

    void _add(int id, T val) {
        for (int i = id; i < len(diff_tree); i += low_bit(i)) {
            diff_tree[i] += val;
            diff_mul_tree[i] += val * id;
        }
    }

    void _add_range(int l, int r, T val) {
        _add(l, val);
        if (r + 1 < len(diff_tree))
            _add(r + 1, -val);
    }

    T _get(int id) {
        T res = 0;
        for (int i = id; i > 0; i -= low_bit(i))
            res += diff_tree[i] * (id + 1) - diff_mul_tree[i];
        return res;
    }


public:
    range_fenvik() = default;

    explicit range_fenvik(int n) {
        diff_tree.resize(n + 1, 0);
        diff_mul_tree.resize(n + 1, 0);
    }

    explicit range_fenvik(const vector<T> &a) {
        diff_tree.resize(len(a) + 1, 0);
        diff_mul_tree.resize(len(a) + 1, 0);
        for (int i = 0; i < len(a); ++i) {
            add(i, a[i]);
        }
    }

    void add(int id, T val) {
        _add_range(id + 1, id + 1, val);
    }

    void add_range(int l, int r, T val) {
        _add_range(l + 1, r + 1, val);
    }


    T get_pref(int id) {
        return _get(id + 1);
    }

    T get(int x) {
        return get(x, x);
    }

    T get(int l, int r) {
        if (l == 0)
            return _get(r + 1);
        return _get(r + 1) - _get(l);
    }
};


int solve(int n, int c, int R, const vec<int> &k, vec<pair<int, int>> segs) {
    vec<int> t(n, 2);
    auto disable = [&](int l, int r) {
        for (int i = l; i <= r; i++) {
            t[i] = 0;
        }
        t[l] = 1;
        t[r] = 1;
    };
    auto findk = [&](int id) {
        if (id == -1) return -1LL;
        for (int i = 0; i < n; i++) {
            id -= t[i];
            if (id <= 0) {
                return i;
            }
        }
        return n;
    };
    for (int i = 0; i < c; i++) {
        int f = findk(segs[i].first * 2 + 1);
        int s = findk(segs[i].second * 2 + 2);
        segs[i] = {f, s};
        disable(f, s);

    }

    int best = 0;
    int id = 0;
    vec<int> v(n);
    v[0] = 1;
    for (int i = 0; i < n - 1; i++)
        v[i + 1] = k[i] > R;
    PrefixSum ps(v);
    range_fenvik<int> d(n);
    
    st1.reset();
    st1.init(n,0);
    auto inc = [&](int l, int r, int val) {
        if (l > r) return;
        d.add_range(l, r, val);
        st1.update(l, r, val);
    };

    for (auto [l, r]: segs) {
        if (ps.get(l, r) > 1) continue;
        if (ps.get(l, r) == 0) {
            inc(l, r, 1);
        }
        if (ps.get(l, r) == 1 and v[l] == 1) {
            inc(l + 1, r, 1);
        }
    }
    int best_id = 0;
    for (int i = 0; i < n; i++) {
        if (chmax(best, st1.get(i, i))) {
            best_id = i;
        }
    }
    return best_id;
//    for (int i = 0; i < n; i++) {
//        vec<int> cur(n, -1);
//        cur[i] = R;
//        int ptr = 0;
//        for (int j = 0; j < n; j++) {
//            if (cur[j] != -1) continue;
//            cur[j] = k[ptr++];
//        }
//        vec<int> b(n);
//        for (int j = 0; j < n; j++) {
//            b[j] = cur[j] > R;
//        }
//
//        int ans = 0;
//
//        PrefixSum ps(b);
//        for (auto [l, r]: segs) {
//            if (r < i or l > i) continue;
//            ans += ps.get(l, r) == 0;
//        }
//        if (chmax(best, ans)) {
//            id = i;
//        }
//    }
    return id;
}

i32 GetBestPosition(i32 N, i32 C, i32 R, i32 *K, i32 *S, i32 *E) {
    vec<int> k(K, K + N - 1);
    vec<pair<int, int>> segs;
    for (int i = 0; i < C; i++) {
        segs.emplace_back(S[i], E[i]);
    }
    return solve(N, C, R, k, segs);
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51