Submission #414671

#	Time	Username	Problem	Language	Result	Execution time	Memory
414671		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];

    Segmenttree()
    {
    }

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

Compilation message (stderr)

tournament.cpp:15:5: error: ISO C++ forbids declaration of 'Segmenttree' with no type [-fpermissive]
   15 |     Segmenttree()
      |     ^~~~~~~~~~~
tournament.cpp: In member function 'int Segmentree::Segmenttree()':
tournament.cpp:17:5: warning: no return statement in function returning non-void [-Wreturn-type]
   17 |     }
      |     ^