Submission #314891

#	Time	Username	Problem	Language	Result	Execution time	Memory
314891		Jarif_Rahman	Werewolf (IOI18_werewolf)	C++17	0 / 100	1174 ms	43320 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
int n, m, q, k;
vector<vector<int>> v;
vector <pair<int, int>> se;
vector <pair<int, int>> lr;
vector <ll> mx, mn;
vector <ll> sth, inx;
void upd(int in, ll x){
    in+=k/2;
    mx[in] = x, mn[in] = x, in/=2;
    while(in > 0){
        mx[in] = max(mx[2*in], mx[2*in+1]);
        mn[in] = min(mn[2*in], mn[2*in+1]);
        in/=2;
    }
}
ll smx(int l, int r){
    l+=k/2, r+=k/2;
    ll s = -inf;
    while(l <= r){
        if(l%2 == 1) s = max(s, mx[l]), l++;
        if(r%2 == 0) s = max(s, mx[r]), r--;
        l/=2, r/=2;
    }
    return s;
}
ll smn(int l, int r){
    l+=k/2, r+=k/2;
    ll s = inf;
    while(l <= r){
        if(l%2 == 1) s = min(s, mn[l]), l++;
        if(r%2 == 0) s = min(s, mn[r]), r--;
        l/=2, r/=2;
    }
    return s;
}
ll gmx(int a, int b, ll x){
    int rr = -1;
    if(smx(a, b) <= x) return rr;
    while(1){
        if(b - a < 2){
            if(smx(a, a) > x) rr = a;
            else rr = b;
            break;
        }
        int md = (a+b)/2;
        if(smx(a, md) > x) b = md;
        else a = md+1;
    }
    return rr;
}
ll gmn(int a, int b, ll x){
    int rr = -1;
    if(smn(a, b) >= x) return rr;
    while(1){
        if(b - a < 2){
            if(smn(b, b) < x) rr = a;
            else rr = a;
            break;
        }
        int md = (a+b)/2;
        if(smn(md, b) < x) a = md;
        else b = md-1;
    }
    return rr;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n = N, m = X.size(), q = S.size();
    for(int i = 0; i < q; i++){
        se.pb({S[i], E[i]});
        lr.pb({L[i], R[i]});
    }
    v = vector<vector<int>>(n);
    for(int i = 0; i < m; i++){
        v[X[i]].pb(Y[i]);
        v[Y[i]].pb(X[i]);
    }

    //-----main
    int a = -1;
    for(int i = 0; i < n; i++) if(v[i].size() == 1){
        a = i;
        break;
    }
    k = 1;
    while(k <= n) k*=2;
    k*=2;
    sth.pb(a);
    mx = vector<ll> (k, 0);
    mn = mx;
    int ls = -1, aa = a;
    while(v[aa].size() > 1 || aa == a){
        for(int x: v[aa]) if(x != ls){
            ls = aa;
            aa = x;
            sth.pb(aa);
            break;
        }
    }
    inx = sth;
    for(int i = 0; i < n; i++){
        upd(i, sth[i]);
        inx[sth[i]] = i;
    }
    vector<int> ans(q);
    for(int i = 0; i < q; i++){
        int s = se[i].f, e = se[i].sc, l = lr[i].f, r = lr[i].sc;
        int ss = inx[s], ee =inx[e];
        if(s < l) ans[i] = 0;
        else if(e > r) ans[i] = 0;
        else if(ss > ee){
            int a = gmx(ee, ss, r), b = gmn(ee, ss, l);
            if(a == -1 || b == -1) ans[i] = 1;
            else if(b - a < 1) ans[i] = 0;
            else ans[i] = 1;
        }
        else{
            int a = gmx(ss, ee, r), b = gmn(ss, ee, l);
            if(a == -1 || b == -1) ans[i] = 1;
            else if(a - b < 1) ans[i] = 0;
            else ans[i] = 1;
        }
    }
    return ans;
}

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