oj.uz

Submission #414810

# Submission time Handle Problem Language Result Execution time Memory
414810 2021-05-31T08:21:12 Z Lam_lai_cuoc_doi Jousting tournament (IOI12_tournament) C++17
100 / 100
 90 ms 6840 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 1e5 + 5;

struct FenwickTree
{
    int a[N];
    int n;

    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }

    void Update(int p, int v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }

    int Get(int p)
    {
        int ans(0);
        for (; p; p -= p & -p)
            ans += a[p];
        return ans;
    }

    int Get(int l, int r)
    {
        return Get(r) - Get(l - 1);
    }
} g;

struct Segmentree
{
    int st[N * 4], lazy[N * 4];

    void Build(int id, int l, int r)
    {
        if (l == r)
        {
            st[id] = 1;
            lazy[id] = -1;
            return;
        }

        Build(id << 1, l, (l + r) / 2);
        Build(id << 1 | 1, (l + r) / 2 + 1, r);
        st[id] = st[id << 1] + st[id << 1 | 1];
        lazy[id] = -1;
    }

    void Push(int id, int l, int r)
    {
        if (lazy[id] != -1)
        {
            int mid = (l + r) / 2;
            st[id << 1] = (mid - l + 1) * lazy[id];
            lazy[id << 1] = lazy[id];
            st[id << 1 | 1] = (r - mid) * lazy[id];
            lazy[id << 1 | 1] = lazy[id];
            lazy[id] = -1;
        }
    }

    void Update(int id, int l, int r, const int &a, const int &b, const int &v)
    {
        if (l > b || r < a)
            return;
        if (l >= a && r <= b)
        {
            st[id] = (r - l + 1) * v;
            lazy[id] = v;
            return;
        }

        Push(id, l, r);

        Update(id << 1, l, (l + r) / 2, a, b, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    int Find(int id, int l, int r, int v)
    {
        while (1)
        {
            if (l == r)
                return l;
            Push(id, l, r);

            if (st[id << 1] >= v)
            {
                id <<= 1;
                r = (l + r) / 2;
            }
            else
            {
                v -= st[id << 1];
                id = id << 1 | 1;
                l = (l + r) / 2 + 1;
            }
        }
        return 0;
    }
} f;

int last[N], id[N];

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e)
{
    f.Build(1, 1, n);
    g.n = n;

    for (int i = 1; i <= n; ++i)
        last[i] = i;

    for (int i = 0; i < c; ++i)
    {
        *(s + i) = f.Find(1, 1, n, ++*(s + i));
        *(e + i) = last[f.Find(1, 1, n, ++*(e + i))];

        //cout << *(s + i) << " " << *(e + i) << "\n";

        last[*(s + i)] = *(e + i);

        f.Update(1, 1, n, *(s + i) + 1, *(e + i), 0);

        id[i] = i;
    }

    sort(id, id + c, [&](const int &x, const int &y)
         { return *(s + x) < *(s + y) || (*(s + x) == *(s + y) && *(e + x) < *(e + y)); });

    int z = c - 1;
    vector<pair<int, int>> v;
    priority_queue<pair<int, int>> x;

    for (int i = 0, j = 0; i < n - 1; ++i)
    {
        while (j < n - 1 && (k[i] <= r) == (k[j] <= r))
            ++j;
        if (k[i] <= r)
            v.emplace_back(i + 1, j + 1);
        i = j - 1;
    }

    reverse(v.begin(), v.end());

    for (auto i : v)
    {
        while (~z && *(s + id[z]) >= i.first)
        {
            x.emplace(*(e + id[z]), *(s + id[z]));
            --z;
        }

        while (x.size() && x.top().first > i.second)
            x.pop();

        while (x.size())
        {
            //cout << x.top().second << " " << x.top().first << "\n";
            g.Update(x.top().second, 1);
            g.Update(x.top().first + 1, -1);
            x.pop();
        }
    }

    pair<int, int> u = {0, 0};

    for (int i = 1; i <= n; ++i)
        u = max(u, make_pair(g.Get(i), -(i - 1)));

    return -u.second;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 704 KB Output is correct
2 Correct 6 ms 916 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 7 ms 972 KB Output is correct
5 Correct 4 ms 976 KB Output is correct
6 Correct 4 ms 976 KB Output is correct
7 Correct 5 ms 976 KB Output is correct
8 Correct 5 ms 976 KB Output is correct
9 Correct 2 ms 864 KB Output is correct
10 Correct 7 ms 976 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3084 KB Output is correct
2 Correct 83 ms 6696 KB Output is correct
3 Correct 20 ms 4164 KB Output is correct
4 Correct 90 ms 6588 KB Output is correct
5 Correct 83 ms 6456 KB Output is correct
6 Correct 73 ms 5652 KB Output is correct
7 Correct 89 ms 6588 KB Output is correct
8 Correct 86 ms 6840 KB Output is correct
9 Correct 30 ms 4212 KB Output is correct
10 Correct 30 ms 4536 KB Output is correct