제출 #1239638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239638		Timosh	늑대인간 (IOI18_werewolf)	C++20	0 / 100	898 ms	30064 KiB

werewolf

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

using namespace std;

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

vector<node> t(8e5);

node merge(node a, node b)
{
  node c;
  c.mx = max(a.mx, b.mx);
  c.mn = min(a.mn, b.mn);
  return c;
}

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

node get(int l, int r, int tl, int tr, 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> p(N), ind(N), vis(N), ans(L.size());
  vector<vector<int>> g(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 cur = 0;
  for (int i = 0; i < N; i++)
    if (g[i].size() == 1)
      cur = i;
  for (int i = 0; i < N; i++)
  {
    p[i] = cur;
    ind[cur] = i;
    vis[cur] = 1;
    for (auto &j : g[cur])
      if (!vis[j])
      {
        cur = j;
        break;
      }
  }
  for (int i = 0; i < N; i++)
    upd(i, p[i], 0, N - 1, 1);
  for (int i = 0; i < L.size(); i++)
  {
    int l = ind[S[i]], r = ind[E[i]], pick = -1;
    if (l <= r)
    {
      while (l <= r)
      {
        int m = (l + r) / 2;
        if (get(l, m, 0, N - 1).mn >= L[i])
          pick = m, l = m + 1;
        else
          r = m - 1;
      }
      if (pick == -1)
        break;
      if (pick == ind[E[i]] || get(pick + 1, ind[E[i]], 0, N - 1).mx <= R[i])
      {
        l = ind[S[i]], r = ind[E[i]];
        swap(l, r);
        while (l <= r)
        {
          int m = (l + r) / 2;
          int mn = get(ind[E[i]], m, 0, N - 1).mn;
          if (mn > R[i])
            l = m + 1;
          else if (mn < L[i])
            r = m - 1;
          else
          {
            ans[i] = 1;
            break;
          }
        }
      }
    }
    else
    {
      swap(l, r);
      while (l <= r)
      {
        int m = (l + r) / 2;
        if (get(l, m, 0, N - 1).mx <= R[i])
          pick = m, l = m + 1;
        else
          r = m - 1;
      }
      if (pick == -1)
        break;
      if (pick == ind[E[i]] || get(pick + 1, ind[S[i]], 0, N - 1).mn >= L[i])
      {
        l = ind[S[i]], r = ind[E[i]];
        while (l <= r)
        {
          int m = (l + r) / 2;
          int mx = get(ind[S[i]], m, 0, N - 1).mx;
          if (mx < L[i])
            l = m + 1;
          else if (mx > R[i])
            r = m - 1;
          else
          {
            ans[i] = 1;
            break;
          }
        }
      }
    }
  }
  return ans;
}

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