oj.uz

답안 #447769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
447769 2021-07-27T13:47:33 Z MilosMilutinovic 늑대인간 (IOI18_werewolf) C++14
0 / 100
 4000 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int n, m, q;
int mx[800005];
int mn[800005];
vi adj[200005], order;

void dfs_ord(int u, int p) {
    order.push_back(u);
    for (int v : adj[u]) {
        if (v != p) dfs_ord(v, u);
    }
}

void Build(int node, int l, int r) {
    if (l == r) {
        mx[node] = order[l];
        mn[node] = order[l];
        return;
    }
    int mid = l + r >> 1;
    Build(node * 2, l, mid);
    Build(node * 2 + 1, mid + 1, r);
    mx[node] = max(mx[node * 2], mx[node * 2 + 1]);
    mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
}

int GetMax(int node, int l, int r, int ll, int rr) {
    if (l > r || l > rr || r < ll) return 0;
    if (ll <= l && r <= rr) return mx[node];
    int mid = l + r >> 1;
    return max(GetMax(node * 2, l, mid, ll, rr), GetMax(node * 2 + 1, mid + 1, r, ll, rr));
}

int GetMin(int node, int l, int r, int ll, int rr) {
    if (l > r || l > rr || r < ll) return 1e9;
    if (ll <= l && r <= rr) return mn[node];
    int mid = l + r >> 1;
    return min(GetMin(node * 2, l, mid, ll, rr), GetMin(node * 2 + 1, mid + 1, r, ll, rr));
}

bool check(pair<int, int> X, pair<int, int> Y) {
    if (X.first <= Y.first && Y.second <= X.second) return true;
    if (Y.first <= X.first && X.second <= Y.second) return true;
    if (X.first <= Y.second && Y.first <= X.first) return true;
    if (Y.first <= X.second && X.first <= Y.first) return true;
    return false;
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    n = N, m = X.size(), q = S.size();
    for (int i = 0; i < m; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    int st = 0;
    for (int i = 0; i < n; i++) {
        if (adj[i].size() == 1) st = i;
    }
    dfs_ord(st, -1);
    Build(1, 0, n - 1);
    vi res(q);
    for (int i = 0; i < q; i++) {
        pair<int, int> X = {S[i], S[i]}, Y = {E[i], E[i]};
        {
            int bot = 0, top = S[i] - 1;
            while (bot <= top) {
                int mid = bot + top >> 1;
                if (GetMin(1, 0, n - 1, mid, S[i] - 1) >= L[i]) {
                    X.first = mid;
                    top = mid - 1;
                } else bot = mid + 1;
            }
        }
        {
            int bot = S[i] + 1, top = n - 1;
            while (bot <= top) {
                int mid = bot + top >> 1;
                if (GetMin(1, 0, n - 1, S[i] + 1, mid) >= L[i]) {
                    X.second = mid;
                    bot = mid + 1;
                } else top = mid - 1;
            }
        }
        {
            int bot = 0, top = E[i] - 1;
            while (bot <= top) {
                int mid = bot + top >> 1;
                if (GetMax(1, 0, n - 1, mid, E[i] - 1) <= R[i]) {
                    Y.first = mid;
                    top = mid - 1;
                } else bot = mid + 1;
            }
        }
        {
            int bot = E[i] + 1, top = n - 1;
            while (bot <= top) {
                int mid = bot + top >> 1;
                if (GetMax(1, 0, n - 1, E[i] + 1, mid) <= R[i]) {
                    Y.second = mid;
                    bot = mid + 1;
                } else top = mid - 1;
            }
        }
        res[i] = (check(X, Y) ? 1 : 0);
    }
    return res;
}

Compilation message

werewolf.cpp: In function 'void Build(int, int, int)':
werewolf.cpp:24:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |     int mid = l + r >> 1;
      |               ~~^~~
werewolf.cpp: In function 'int GetMax(int, int, int, int, int)':
werewolf.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid = l + r >> 1;
      |               ~~^~~
werewolf.cpp: In function 'int GetMin(int, int, int, int, int)':
werewolf.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid = l + r >> 1;
      |               ~~^~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:71:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |                 int mid = bot + top >> 1;
      |                           ~~~~^~~~~
werewolf.cpp:81:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |                 int mid = bot + top >> 1;
      |                           ~~~~^~~~~
werewolf.cpp:91:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |                 int mid = bot + top >> 1;
      |                           ~~~~^~~~~
werewolf.cpp:101:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |                 int mid = bot + top >> 1;
      |                           ~~~~^~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 345 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 345 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4089 ms 35928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 345 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -