Submission #116255

#	Time	Username	Problem	Language	Result	Execution time	Memory
116255		mirbek01	Werewolf (IOI18_werewolf)	C++11	0 / 100	4086 ms	59000 KiB

werewolf

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

using namespace std;

const int N = 4e5 + 2;

int ver[N], pos[N], n, t[2][N * 4];
vector <int> g[N];

void upd(int pos, int val, int tp, int v = 1, int tl = 1, int tr = n){
      if(tl == tr){
            t[tp][v] = ver[tl];
      } else {
            int tm = (tl + tr) >> 1;
            if(pos <= tm)
                  upd(pos, val, tp, v << 1, tl, tm);
            else
                  upd(pos, val, tp, v << 1 | 1, tm + 1, tr);
            if(tp)
                  t[tp][v] = max(t[tp][v << 1], t[tp][v << 1 | 1]);
            else
                  t[tp][v] = min(t[tp][v << 1], t[tp][v << 1 | 1]);
      }
}

int get(int l, int r, int tp, int v = 1, int tl = 1, int tr = n){
      if(tl > r || l > tr){
            if(tp)
                  return 0;
            else
                  return 2e9;
      }
      if(l <= tl && tr <= r)
            return t[tp][v];
      int tm = (tl + tr) >> 1;
      if(tp)
            return max(get(l, r, tp, v << 1, tl, tm),
                        get(l, r, tp, v << 1 | 1, tm + 1, tr));
      else
            return min(get(l, r, tp, v << 1, tl, tm),
                        get(l, r, tp, v << 1 | 1, tm + 1, tr));
}

void dfs(int v, int par = -1){
      ver[++ n] = v;
      for(int to : g[v]){
            if(to == par)
                  continue;
            dfs(to, v);
      }
}

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 = S.size();
      int m = X.size();
      vector <int> A(q);

      for(int i = 0; i < m; i ++){
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
      }

      for(int i = 0; i < N; i ++){
            if(g[i].size() == 1){
                  dfs(i);
                  break;
            }
      }

      for(int i = 0; i < N; i ++){
            pos[ver[i]] = i + 1;
            upd(i + 1, ver[i], 0);
            upd(i + 1, ver[i], 1);
      }

      for(int i = 0; i < q; i ++){
            int l1, l2, r1, r2;
            l1 = pos[S[i]], r1 = pos[S[i]];
            l2 = pos[E[i]], r2 = pos[E[i]];
            int lo = 1, hi = l1, ret = l1;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(get(md, l1, 0) >= L[i])
                        hi = md - 1, ret = md;
                  else
                        lo = md + 1;
            }
            l1 = ret;
            lo = r1, hi = n;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(get(r1, md, 0) >= L[i])
                        lo = md + 1, ret = md;
                  else
                        hi = md - 1;
            }
            r1 = ret;
            lo = 1, hi = l2, ret = l2;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(get(md, l2, 1) <= R[i])
                        hi = md - 1, ret = md;
                  else
                        lo = md + 1;
            }
            l2 = ret;
            lo = r2, hi = n;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(get(r2, md, 1) <= R[i])
                        lo = md + 1, ret = md;
                  else
                        hi = md - 1;
            }
            r2 = ret;
            if(max(l1, l2) <= min(r1, r2))
                  A[i] = 1;
      }

      return A;
}

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