Submission #131555

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

seats

#include "werewolf.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1e8;
 
struct segTree {
  int N; vector<int> lows,highs;
  segTree(int N): N(N), lows(2*N,INF), highs(2*N,-1) {}
  pair<int,int> find(int a, int b) {
    a += N; b += N;
    if (a > b) swap(a,b);
    int low = INF, high = -1;
    while (a <= b) {
      if (a%2 == 1) {
        low = min(low,lows[a]);
        high = max(high,highs[a]);
        a++;
      }
      if (b%2 == 0) {
        low = min(low,lows[b]);
        high = max(high,highs[b]);
        b--;
      }
      a /= 2; b /= 2;
    }
    return make_pair(low,high);
  }
  void upd(int i, int x) {
    i += N;
    lows[i] = highs[i] = x;
    for (i /= 2; i > 0; i /= 2) {
      lows[i] = min(lows[2*i],lows[2*i+1]);
      highs[i] = max(highs[2*i],highs[2*i+1]);
    }
  }
};
 
// void dfs(int u, int N, vector<vector<int>> &adj, vector<int> &explored) {
//   for (int v: adj[u]) {
//     if (explored[v]) continue;
//     dfs(v);
//   }
// }
 
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
 
  int Q = S.size();
 
  vector<vector<int>> adj(N);
  
  for (int i = 0; i < N; i++) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
 
  int end;
  for (int i = 0; i < N; i++) if (adj[i].size() == 1) end = i;
 
  int j = 0; 
  int cur = end; int pre = -1;
 
  vector<int> order {end}, index(N);
  segTree st(N);
  st.upd(0,end);
 
  for (int i = 1; i < N; i++) {
    int nxt = (adj[cur][0] == pre ? adj[cur][1] : adj[cur][0]);
    pre = cur;
    cur = nxt;
    index[nxt] = order.size();
    order.push_back(nxt);
   // cout << i << " " << nxt << "\n";
    st.upd(i,nxt);
  }
 
  vector<int> A(Q,0);
 
  
 
  for (int q = 0; q < Q; q++) {
 
    S[q] = index[S[q]];
    E[q] = index[E[q]];
 
    int swap = 1;
    if (S[q] > E[q]) {
      swap = -1;
    }
 
    int high = abs(E[q]-S[q])+1;
 
    //find the most human can walk from start
 
    int goHuman = -1; 
 
    for (int b = high/2; b > 0; b /= 2) {
      while (goHuman + b < high && st.find(S[q],S[q]+(goHuman+b)*swap).first >= L[q]) goHuman += b; 
    }
 
    //find the most wolf can walk from end
 
    int goWolf = -1; 
 
    for (int b = high/2; b > 0; b /= 2) {
      while (goWolf + b < high && st.find(E[q]-(goWolf+b)*swap,E[q]).second <= R[q]) goWolf += b;
    }
 
   // cout << st.find(S[q],S[q]+(0)*swap).first << "\n";
 
     //cout << goHuman << " " << goWolf << "\n";
 
    if (goWolf >= 0 && goHuman >= 0 && goWolf+goHuman >= abs(E[q]-S[q])) A[q] = 1;
    else A[q] = 0;
  }
 
  return A;
}

Compilation message (stderr)

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