Submission #1031385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031385		0pt1mus23	Werewolf (IOI18_werewolf)	C++14	0 / 100	365 ms	524288 KiB

werewolf

#include "werewolf.h"
#pragma GCC optimize("O3", "inline")
#define skillissue <bits/stdc++.h>
#define ultra_mal std
#include skillissue
using namespace ultra_mal;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ins insert
#define pb push_back
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define hash FhashF
const int mod = 1e9 +7, sze = 2e5 +300, inf = INT_MAX, P = 1453;
vector<int> graph[sze];
vector<int> arr,arr2;
int idx[sze],idx2[sze];
const int L  = 20;
int lg[sze];
int dpmx[L][sze],dpmn[L][sze];
int dpmx2[L][sze],dpmn2[L][sze];
void dfs(int node,int par=-1){
    idx[node]=arr.size();
    arr.pb(node);
    for(auto v:graph[node]){
        if(v!=par){
            dfs(v,node);
        }
    }
}
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();
    for(int i=2;i<sze;i++){
        lg[i]=lg[i/2]+1;
    }
    vector<int> A(Q);
    int m = X.size();
    for(int i=0;i<m;i++){
        graph[X[i]].pb(Y[i]);
        graph[Y[i]].pb(X[i]);
    }
    int x =0;
    for(int i =0;i<n;i++){
        if(graph[i].size()==1){
            x=i;
            break;
        }
    }
    dfs(x);
    arr2=arr;
    int j= 0;
    reverse(all(arr2));
    for(auto v:arr2){
        idx2[v]=j++;
    }
    j=0;// fobi
    for(int i=0;i<n;i++){
        dpmn[0][i]=arr[i];
        dpmx[0][i]=arr[i];
        dpmn2[0][i]=arr2[i];
        dpmx2[0][i]=arr2[i];
    }
    for(int i=1;i<20;i++){
        for(int j=0;j + (1<<i)<=n;j++){
            dpmn[i][j]= min(dpmn[i-1][j],dpmn[i-1][j + (1<<(i-1))]);
            dpmx[i][j]= max(dpmx[i-1][j],dpmx[i-1][j + (1<<(i-1))]);
            dpmn2[i][j]= min(dpmn2[i-1][j],dpmn2[i-1][j + (1<<(i-1))]);
            dpmx2[i][j]= max(dpmx2[i-1][j],dpmx2[i-1][j + (1<<(i-1))]);
        }
    }
    auto qry = [&](int l,int r) -> pii {
        int len =lg[r-l+1];
        return {    min(dpmn[len][l],dpmn[len][r - (1<<len)+1]),
                    max(dpmx[len][l],dpmx[len][r - (1<<len)+1])};
    };
    auto qry2 = [&](int l,int r) -> pii {
        int len =lg[r-l+1];
        return {    min(dpmn2[len][l],dpmn2[len][r - (1<<len)+1]),
                    max(dpmx2[len][l],dpmx2[len][r - (1<<len)+1])};
    };
    for(int i=0;i<Q;i++){
        A[i]=0;

        int start = S[i];
        int finish = E[i];

        int wl = L[i];
        int wr = R[i];

        int l,r,ans = -1;
        if(idx[start]<idx[finish]){
            l = idx[start];
            r = idx[finish];

            while(l<=r){
                int mid = (l+r)/2;
                pii res = qry(idx[start],mid);
                if(res.second <= wr){
                    l=mid+1;
                    ans=max(ans,mid);
                }
                else{
                    r=mid-1;
                }
            }

            if(ans!=-1 && qry(ans,idx[finish]).first>=wl && arr[ans]>=wl && arr[ans]<=wr){
                A[i]=1;
            }

        } 
        else{ // reverse
            l = idx2[start];
            r = idx2[finish];
            

            while(l<=r){
                int mid = (l+r)/2;
                pii res = qry2(idx2[start],mid);
                if(res.second <= wr){
                    l=mid+1;
                    ans=max(ans,mid);
                }
                else{
                    r=mid-1;
                }
            }

            if(ans!=-1 && qry2(ans,idx2[finish]).first>=wl && arr2[ans]>=wl && arr2[ans]<=wr){
                A[i]=1;
            }
        }

    }
    
    return A;
}

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