Submission #1241150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241150		kunzaZa183	Werewolf (IOI18_werewolf)	C++20	100 / 100	1222 ms	237388 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S,
                           vector<int> E, vector<int> L, vector<int> R) {
  vector<pair<int, int>> vpii;
  for (int i = 0; i < X.size(); i++)
    vpii.push_back(minmax(X[i], Y[i]));
  vector<array<int, 5>> vai5;
  for (int i = 0; i < S.size(); i++)
    vai5.push_back({i, S[i], E[i], L[i], R[i]});

  function<int(int, vector<int> &)> fvivi = [&](int cur, vector<int> &par) {
    if (par[cur] == cur)
      return cur;
    return par[cur] = fvivi(par[cur], par);
  };

  int ct = -1;
  function<void(int, vector<vector<int>> &, vector<int> &, vector<int> &)> dfs =
      [&](int cur, vector<vector<int>> &adj, vector<int> &l, vector<int> &r) {
        if (adj[cur].empty()) {
          ct++;
          l[cur] = r[cur] = ct;
          return;
        }
        l[cur] = ct + 1;
        for (auto a : adj[cur])
          dfs(a, adj, l, r);
        r[cur] = ct;
      };

  sort(vpii.begin(), vpii.end(),
       [&](pair<int, int> a, pair<int, int> b) { return a.first > b.first; });

  vector<int> parvi1(N);
  iota(parvi1.begin(), parvi1.end(), 0);

  vector<vector<int>> adj1(N);
  for (auto [a, b] : vpii) {
    a = fvivi(a, parvi1), b = fvivi(b, parvi1);
    parvi1[a] = parvi1[b] = adj1.size();
    parvi1.push_back(parvi1.size());

    adj1.push_back({});
    adj1.back().push_back(a);
    if (a != b)
      adj1.back().push_back(b);
  }

  vector<int> l1(parvi1.size()), r1(parvi1.size());
  dfs(parvi1.size() - 1, adj1, l1, r1);

  parvi1 = vector<int>(N);
  iota(parvi1.begin(), parvi1.end(), 0);
  int in = 0;
  sort(vai5.begin(), vai5.end(),
       [&](array<int, 5> a, array<int, 5> b) { return a[3] > b[3]; });
  vector<int> ql1(S.size()), qr1(S.size());
  for (auto [a, b] : vpii) {
    while (in < vai5.size() && vai5[in][3] > a) {
      ql1[vai5[in][0]] = l1[fvivi(vai5[in][1], parvi1)],
      qr1[vai5[in][0]] = r1[fvivi(vai5[in][1], parvi1)];
      in++;
    }

    a = fvivi(a, parvi1), b = fvivi(b, parvi1);
    parvi1[a] = parvi1[b] = parvi1.size();
    parvi1.push_back(parvi1.size());
  }

  while (in < vai5.size()) {
    ql1[vai5[in][0]] = l1[fvivi(vai5[in][1], parvi1)],
    qr1[vai5[in][0]] = r1[fvivi(vai5[in][1], parvi1)];
    in++;
  }

  vector<int> parvi2(N);
  iota(parvi2.begin(), parvi2.end(), 0);

  sort(vpii.begin(), vpii.end(),
       [&](pair<int, int> a, pair<int, int> b) { return a.second < b.second; });

  vector<vector<int>> adj2(N);
  for (auto [a, b] : vpii) {
    a = fvivi(a, parvi2), b = fvivi(b, parvi2);
    parvi2[a] = parvi2[b] = adj2.size();
    parvi2.push_back(parvi2.size());

    adj2.push_back({});
    adj2.back().push_back(a);
    if (a != b)
      adj2.back().push_back(b);
  }

  vector<int> l2(parvi2.size()), r2(parvi2.size());
  ct = -1;
  dfs(parvi2.size() - 1, adj2, l2, r2);

  parvi2 = vector<int>(N);
  iota(parvi2.begin(), parvi2.end(), 0);
  in = 0;
  sort(vai5.begin(), vai5.end(),
       [&](array<int, 5> a, array<int, 5> b) { return a[4] < b[4]; });
  vector<int> ql2(S.size()), qr2(S.size());
  for (auto [a, b] : vpii) {
    while (in < vai5.size() && vai5[in][4] < b) {
      ql2[vai5[in][0]] = l2[fvivi(vai5[in][2], parvi2)],
      qr2[vai5[in][0]] = r2[fvivi(vai5[in][2], parvi2)];
      in++;
    }

    a = fvivi(a, parvi2), b = fvivi(b, parvi2);
    parvi2[a] = parvi2[b] = parvi2.size();
    parvi2.push_back(parvi2.size());
  }

  while (in < vai5.size()) {
    ql2[vai5[in][0]] = l2[fvivi(vai5[in][2], parvi2)],
    qr2[vai5[in][0]] = r2[fvivi(vai5[in][2], parvi2)];
    in++;
  }

  vector<array<int, 3>> order(N);
  vector<pair<int, int>> points(N);
  for (int i = 0; i < N; i++)
    points[i] = {l1[i], l2[i]};
  sort(points.begin(), points.end());
  for (int i = 0; i < N; i++)
    order[i] = {i, points[i].first, points[i].second};
  auto ocmp = [&](array<int, 3> a, array<int, 3> b) { return a[2] < b[2]; };
  sort(order.begin(), order.end(), ocmp);

  vector<int> ans(L.size());

  struct node {
    int ct = 0;
    node *l = NULL, *r = NULL;
  };

  vector<node *> vn;

  function<node *(int, int)> build = [&](int curl, int curr) {
    auto tmp = new node;
    if (curl == curr) {
      return tmp;
    }
    int mid = (curl + curr) / 2;
    tmp->l = build(curl, mid), tmp->r = build(mid + 1, curr);
    return tmp;
  };

  vn.push_back(build(0, N - 1));

  function<node *(node *, int, int, int)> insert = [&](node *n, int curl,
                                                       int curr, int in) {
    auto tmp = new node;
    if (curl == curr) {
      tmp->ct = 1;
      return tmp;
    }
    int mid = (curl + curr) / 2;
    if (in <= mid) {
      tmp->r = n->r;
      tmp->l = insert(n->l, curl, mid, in);
    } else {
      tmp->l = n->l;
      tmp->r = insert(n->r, mid + 1, curr, in);
    }
    tmp->ct = tmp->l->ct + tmp->r->ct;
    return tmp;
  };

  for (auto [in, x, y] : order) {
    vn.push_back(insert(vn.back(), 0, N - 1, in));
  }

  int ql, qr;
  function<int(node *, int, int)> qry = [&](node *n, int curl, int curr) {
    if (curl > qr || curr < ql)
      return 0;
    if (ql <= curl && curr <= qr)
      return n->ct;

    return qry(n->l, curl, (curl + curr) / 2) +
           qry(n->r, (curl + curr) / 2 + 1, curr);
  };

  for (int i = 0; i < S.size(); i++) {
    ql = lower_bound(points.begin(), points.end(), make_pair(ql1[i], -1)) -
            points.begin(),
        qr = upper_bound(points.begin(), points.end(),
                        make_pair(qr1[i], INT_MAX)) -
            points.begin() - 1;

    int l = lower_bound(order.begin(), order.end(),
                         array<int, 3>({-1, -1, ql2[i]}), ocmp) -
             order.begin(),
        r = upper_bound(order.begin(), order.end(),
                         array<int, 3>({-1, -1, qr2[i]}), ocmp) -
             order.begin();

    ans[i] = min(1, qry(vn[r], 0, N - 1) - qry(vn[l], 0, N - 1));
  }

  return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51