Submission #414672

#	Time	Username	Problem	Language	Result	Execution time	Memory
414672		Lam_lai_cuoc_doi	Jousting tournament (IOI12_tournament)	C++17	Compilation error	0 ms	0 KiB

tournament

#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 = 2e5 + 5;

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

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

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

    vector<pair<int, int>> v;
    v.reserve(n);

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

    sort(v.begin(), v.end(), greater<pair<int, int>>());

    priority_queue<int> x;
    pair<int, int> u = {0, 0};
    int z = c - 1;

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

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

        u = max(u, make_pair((int)x.size(), i.first - 1));
    }

    return u.second;
}

int n, c, r, k[N], s[N], e[N];

void Read()
{
    cin >> n >> c >> r;
    for (int i = 0; i < n - 1; ++i)
        cin >> k[i];

    for (int i = 0; i < c; ++i)
        cin >> s[i] >> e[i];
}

void Solve()
{
    cout << GetBestPosition(n, c, r, k, s, e);
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccsqqVON.o: in function `main':
tournament.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccRqxrO.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status