Submission #1239721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239721		Timosh	Werewolf (IOI18_werewolf)	C++20	34 / 100	1658 ms	589824 KiB

werewolf

#include "bits/stdc++.h"
#include "werewolf.h"

using namespace std;

struct node
{
  int mn, mx;
  node()
  {
    mn = 1e9;
    mx = 0;
  }
};

node merge(node a, node b)
{
  node c;
  c.mx = max(a.mx, b.mx);
  c.mn = min(a.mn, b.mn);
  return c;
}
int n;
vector<node> t(8e5);

void upd(int pos, int x, int l = 0, int r = n - 1, int i = 1)
{
  if (l == r)
    t[i].mx = t[i].mn = x;
  else
  {
    int m = (l + r) / 2;
    if (pos <= m)
      upd(pos, x, l, m, i * 2);
    else
      upd(pos, x, m + 1, r, i * 2 + 1);
    t[i] = merge(t[i * 2], t[i * 2 + 1]);
  }
}

node get(int l, int r, int tl = 0, int tr = n - 1, int i = 1)
{
  if (l > tr || tl > r)
    return t[0];
  if (l <= tl && tr <= r)
    return t[i];
  int m = (tl + tr) / 2;
  return merge(get(l, r, tl, m, i * 2), get(l, r, m + 1, tr, i * 2 + 1));
}

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<int> vis(N), p, ind(N), ans(L.size());
  vector<vector<int>> g(N);
  int i;
  n = N;
  for (int i = 0; i < X.size(); i++)
    g[X[i]].push_back(Y[i]);
  for (int i = 0; i < X.size(); i++)
    g[Y[i]].push_back(X[i]);
  int start = 0;
  while (g[start].size() != 1)
    start++;
  auto dfs = [&](auto dfs, int node, int par) -> void
  {
    p.push_back(node);
    for (auto &x : g[node])
      if (x != par)
        dfs(dfs, x, node);
  };
  dfs(dfs, start, -1);
  for (int i = 0; i < N; i++)
    upd(i, p[i]), ind[p[i]] = i;
  for (int i = 0; i < S.size(); i++)
  {
    S[i] = ind[S[i]];
    E[i] = ind[E[i]];
    int l = S[i];
    int r = E[i];
    if (l <= r)
    {
      int last_big = -1, first_small = N;
      while (l <= r)
      {
        int m = (l + r) / 2;
        if (get(m, E[i]).mx > R[i])
          last_big = m, l = m + 1;
        else
          r = m - 1;
      }
      l = S[i], r = E[i];
      while (l <= r)
      {
        int m = (l + r) / 2;
        if (get(S[i], m).mn < L[i])
          first_small = m, r = m - 1;
        else
          l = m + 1;
      }
      if (last_big < first_small - 1)
        ans[i] = 1;
    }
    else
    {
      swap(l, r);
      int last_small = -1, first_big = N;
      while (l <= r)
      {
        int m = (l + r) / 2;
        if (get(m, S[i]).mn < L[i])
          last_small = m, l = m + 1;
        else
          r = m - 1;
      }
      l = E[i], r = S[i];
      while (l <= r)
      {
        int m = (l + r) / 2;
        if (get(E[i], m).mx > R[i])
          first_big = m, r = m - 1;
        else
          l = m + 1;
      }
      if (last_small < first_big - 1)
        ans[i] = 1;
    }
  }
  return ans;
}

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