Submission #491069

#	Time	Username	Problem	Language	Result	Execution time	Memory
491069		dung11112003	Jousting tournament (IOI12_tournament)	C++11	0 / 100	51 ms	4432 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

template <class T>
struct SegTree
{
    T const identity;
    std::vector <T> f;
    T (* const combine)(T, T);
    SegTree(int n, T const identity, T (* const combine)(T, T)) : identity(identity), f(n * 4, identity), combine(combine) {}
    void init(int n, T val)
    {
        f.assign(n * 4, val);
    }
    template <class H>
    void build(int x, int lo, int hi, const H construct)
    {
        if (lo == hi)
        {
            f[x] = construct(lo);
            return;
        }
        int mid = (lo + hi) / 2;
        build(x * 2, lo, mid, construct);
        build(x * 2 + 1, mid + 1, hi, construct);
        f[x] = combine(f[x * 2], f[x * 2 + 1]);
    }
    void set(int x, int lo, int hi, int idx, T val)
    {
        if (lo == hi)
        {
            f[x] = val;
            return;
        }
        int mid = (lo + hi) / 2;
        if (idx <= mid)
        {
            set(x * 2, lo, mid, idx, val);
        }
        else
        {
            set(x * 2 + 1, mid + 1, hi, idx, val);
        }
        f[x] = combine(f[x * 2], f[x * 2 + 1]);
    }
    void update(int x, int lo, int hi, int idx, T val)
    {
        if (lo == hi)
        {
            f[x] = combine(f[x], val);
            return;
        }
        int mid = (lo + hi) / 2;
        if (idx <= mid)
        {
            update(x * 2, lo, mid, idx, val);
        }
        else
        {
            update(x * 2 + 1, mid + 1, hi, idx, val);
        }
        f[x] = combine(f[x * 2], f[x * 2 + 1]);
    }
    T query(int x, int lo, int hi, int L, int R)
    {
        if (lo > R || hi < L)
        {
            return identity;
        }
        if (lo >= L && hi <= R)
        {
            return f[x];
        }
        int mid = (lo + hi) / 2;
        return combine(query(x * 2, lo, mid, L, R), query(x * 2 + 1, mid + 1, hi, L, R));
    }
};

int GetBestPosition(int n, int m, int K, int *a, int *S, int *E)
{
    vector <int> f(n + 1);
    auto update = [&](int x, int d)
    {
        for (; x <= n; x += x & -x)
        {
            f[x] += d;
        }
    };
    auto kth = [&](int k) -> int
    {
        int pos = 0;
        for (int mask = 1 << 20; mask; mask >>= 1)
        {
            if (pos + mask <= n && f[pos + mask] < k)
            {
                k -= f[pos += mask];
            }
        }
        return ++pos;
    };
    for (int i = 1; i <= n; i++)
    {
        update(i, 1);
    }
    vector <array <int, 3>> rounds;
    vector <int> sum(n + 1, 1);
    for (int i = 0; i < m; i++)
    {
        S[i]++;
        E[i]++;
        int L = kth(S[i]), R = kth(E[i]);
        R += sum[R] - 1;
        for (int j = E[i]; j > S[i]; j--)
        {
            int pos = kth(j);
            update(pos, -1);
            sum[L] += sum[pos];
        }
        rounds.push_back({L, R, i});
    }
    vector <int> threats = {0};
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] > K)
        {
            threats.push_back(i + 1);
        }
    }
    threats.push_back(n);
    sort(rounds.begin(), rounds.end());
    int id = 0;
    vector <int> alive(n + 1);
    SegTree <int> seg(n, 1e9, [](int x, int y) -> int
    {
        return (x < y ? x : y);
    });
    seg.init(n, 1e9);
    for (int i = 0; i < (int)threats.size() - 1; i++)
    {
        while (id < (int)rounds.size() && rounds[id][0] <= threats[i])
        {
            seg.update(1, 1, n, rounds[id][1], rounds[id][2]);
            id++;
        }
        for (int j = threats[i] + 1; j <= threats[i + 1]; j++)
        {
            alive[j] = seg.query(1, 1, n, j, n);
        }
    }
    sort(rounds.begin(), rounds.end(), [](array <int, 3> x, array <int, 3> y)
    {
        return x[1] > y[1];
    });
    id = 0;
    seg.init(n, 1e9);
    for (int i = (int)threats.size() - 2; ~i; i--)
    {
        while (id < (int)rounds.size() && rounds[id][1] >= threats[i + 1] + 1)
        {
            seg.update(1, 1, n, rounds[id][1], rounds[id][2]);
            id++;
        }
        for (int j = threats[i] + 1; j <= threats[i + 1]; j++)
        {
            alive[j] = min(alive[j], seg.query(1, 1, n, 1, j));
        }
    }
    vector <int> matches(n + 1);
    vector <vector <int>> queries(m);
    for (int i = 1; i <= n; i++)
    {
        if (alive[i] == 0)
        {
            matches[i] = 0;
        }
        else
        {
            queries[min(alive[i], m) - 1].push_back(i);
        }
    }
    sort(rounds.begin(), rounds.end(), [](array <int, 3> x, array <int, 3> y)
    {
        return x[2] < y[2];
    });
    auto prefix = [&](int x)
    {
        int ans = 0;
        for (; x > 0; x &= x - 1)
        {
            ans += f[x];
        }
        return ans;
    };
    f.assign(n + 1, 0);
    for (int i = 0; i < m; i++)
    {
        update(rounds[i][0], 1);
        update(rounds[i][1] + 1, -1);
        for (auto &x: queries[i])
        {
            matches[x] = prefix(x);
        }
    }
    int wins = -1, pos = -1;
    for (int i = 1; i <= n; i++)
    {
        if (matches[i] > wins)
        {
            wins = matches[i];
            pos = i - 1;
        }
    }
    return pos;
}

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