Submission #277957

#	Time	Username	Problem	Language	Result	Execution time	Memory
277957		hamerin	Seats (IOI18_seats)	C++17	Compilation error	0 ms	0 KiB

seats

#include "werewolf.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

const i64 PINF = numeric_limits<int>::max();
const i64 NINF = numeric_limits<int>::min();

class disjointSet {
   public:
    vector<int> p;

    disjointSet() = default;
    explicit disjointSet(int N) {
        p.clear();
        p.resize(N);
        for (int i = 0; i < N; i++) p[i] = i;
    }

    int find(int u) { return p[u] = (p[u] == u ? u : find(p[u])); }

    void mer(int u, int v) { p[find(v)] = find(u); }

    bool sset(int u, int v) { return find(u) == find(v); }
};


namespace Helper {
    vector<int> inversePerm(const vector<int> &per) {
        int N = per.size();
        vector<int> ret(N);
        for (int i = 0; i < N; i++) ret[per[i]] = i;

        return ret;
    }

    vector<int> inversePerm(vector<int> &&per) {
        int N = per.size();
        vector<int> ret(N);
        for (int i = 0; i < N; i++) ret[per[i]] = i;

        return ret;
    }
}  // namespace Helper


class tree {
   public:
    vector<vector<int>> tr, spt;
    vector<int> in, out;
    int ord;

    tree() = default;
    explicit tree(int N) {
        tr.resize(N), spt.resize(N);
        in.resize(N), out.resize(N);
        ord = 0;
    }

    void emplace_edge(int p, int c) {
        tr[p].emplace_back(c);
    }

    void dfs_order(int h) {
        in[h] = ++ord;
        for (auto t : tr[h]) dfs_order(t);
        out[h] = ord;
    }

    void genSparseTable(int h, int p) {
        if (p >= 0) {
            int sn = 1;
            spt[h].emplace_back(p);
            while (true) {
                const auto &sppt = spt[spt[h][sn - 1]];
                if (sppt.size() < sn) break;
                spt[h].emplace_back(sppt[sn - 1]);
                ++sn;
            }
        }

        for (auto t : tr[h]) genSparseTable(t, h);
    }

    int find1(int h, int li) {
        int p = spt[h].size() - 1;
        while (true) {
            if (h == li) return h;
            if (spt[h][0] > li) return h;

            while (spt[h][p] > li) --p;
            h = spt[h][p];
            p = min(p, (int)spt[h].size() - 1);
        }
    }

    int find2(int h, int li) {
        int p = spt[h].size() - 1;
        while (true) {
            if (h == li) return h;
            if (spt[h][0] < li) return h;

            while (spt[h][p] < li) --p;
            h = spt[h][p];
            p = min(p, (int)spt[h].size() - 1);
        }
    }
};


class segTree {
   public:
    vector<int> vl;
    int N;

    segTree() = default;
    segTree(int _N) {
        vl.resize(1 << 19, NINF);
        N = _N;
    }

    void update(int s, int e, int n, int t, int ne) {
        if (s == e) {
            vl[n] = ne;
            return;
        }

        int m = (s + e) >> 1;
        int k = n << 1;
        if (t <= m)
            update(s, m, k, t, ne);
        else
            update(m + 1, e, k + 1, t, ne);

        vl[n] = max(vl[k], vl[k + 1]);
    }

    void update(int t, int ne) { update(1, N, 1, t, ne); }

    int query(int s, int e, int n, int l, int r) {
        if (r < s || e < l) return NINF;
        if (l <= s && e <= r) return vl[n];

        int m = (s + e) >> 1;
        int k = n << 1;
        return max(query(s, m, k, l, r), query(m + 1, e, k + 1, l, r));
    }

    int query(int l, int r) { return query(1, N, 1, l, r); }
};


using qi = tuple<int, int, int, int>;
using pei = tuple<int, int, int, int, int>;

vector<int> check_validity(int N,
                           vector<int> X, vector<int> Y,
                           vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int Q = (int)S.size();
    int M = (int)X.size();

    vector<vector<int>> graph(N);
    for (int i = 0; i < M; i++) {
        graph[X[i]].emplace_back(Y[i]);
        graph[Y[i]].emplace_back(X[i]);
    }


    tree tree1(N);
    disjointSet dS1(N);
    for (int i = 1; i < N; i++) {
        set<int> toemplace;
        for (auto j : graph[i]) {
            if (j < i) toemplace.emplace(dS1.find(j));
        }

        for (auto j : toemplace) {
            dS1.mer(i, j);
            tree1.emplace_edge(i, j);
        }
    }

    tree1.dfs_order(N - 1);
    tree1.genSparseTable(N - 1, -1);

    tree tree2(N);
    disjointSet dS2(N);
    for (int i = N - 2; i >= 0; i--) {
        set<int> toemplace;
        for (auto j : graph[i]) {
            if (j > i) toemplace.emplace(dS2.find(j));
        }

        for (auto j : toemplace) {
            dS2.mer(i, j);
            tree2.emplace_edge(i, j);
        }
    }

    tree2.dfs_order(0);
    tree2.genSparseTable(0, -1);


    vector<pi> points;
    for (int i = 0; i < N; i++) {
        points.emplace_back(tree1.in[i], tree2.in[i]);
    }
    sort(iterall(points));

    vector<qi> queries(Q);
    for (int i = 0; i < Q; i++) {
        queries[i] = {S[i], E[i], L[i], R[i]};
    }

    vector<pei> rectq;  // lx, hx, ly, hy, idx
    for (int i = 0; i < Q; i++) {
        auto [s, e, l, r] = queries[i];
        auto n1 = tree1.find1(e, r);
        auto n2 = tree2.find2(s, l);
        rectq.emplace_back(tree1.in[n1], tree1.out[n1],
                           tree2.in[n2], tree2.out[n2], i);
    }
    sort(iterall(rectq), [](const pei &l, const pei &r) {
        return get<1>(l) < get<1>(r);
    });


    vector<int> ret(Q);
    int ptr = 0;
    auto sT = segTree(N);
    for (auto [lx, hx, ly, hy, idx] : rectq) {
        while (ptr < N && points[ptr].first <= hx) {
            auto [x, y] = points[ptr];
            sT.update(y, x);
            ++ptr;
        }

        if (sT.query(ly, hy) >= lx) ret[idx] = 1;
    }

    return ret;
}

Compilation message (stderr)

seats.cpp:1:10: fatal error: werewolf.h: No such file or directory
    1 | #include "werewolf.h"
      |          ^~~~~~~~~~~~
compilation terminated.