제출 #598359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598359		Dremix10	늑대인간 (IOI18_werewolf)	C++17	0 / 100	291 ms	32408 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <assert.h>
#include <numeric>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define p2(x,y) {}
    #define pp(x) {}
    #define pv(x) {}
    #define ppv(x) {}
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 2e18;
const int MOD = 1e9+7;
const int NN = 3e5+1;


vector<vector<int> > a;
bool flag;



int mn[2][NN*4],mx[2][NN*4];
int arr[2][NN],posi[NN];
bool mt = false;

void buildmn(int s, int e, int idx){
    if(s==e){
        mn[mt][idx] = arr[mt][idx];
        return;
    }
    int mid = (s+e)/2;
    buildmn(s,mid,idx*2);
    buildmn(mid+1,e,idx*2+1);
    mn[mt][idx] = min(mn[mt][idx*2],mn[mt][idx*2+1]);
}

void buildmx(int s, int e, int idx){
    if(s==e){
        mx[mt][idx] = arr[mt][idx];
        return;
    }
    int mid = (s+e)/2;
    buildmx(s,mid,idx*2);
    buildmx(mid+1,e,idx*2+1);
    mx[mt][idx] = max(mx[mt][idx*2],mx[mt][idx*2+1]);
}

int lo(int s, int e, int idx, int l, int x){
    if(e < l)return -1;
    if(s==e){
        assert(mn[mt][idx] < x);
        return s;
    }
    
    int mid = (s+e)/2;
    int res = -1;
    if(mn[mt][idx*2] < x){
        res = lo(s,mid,idx*2,l,x);
    }

    if(res == -1 && mn[mt][idx*2+1] < x){
        res = lo(mid+1,e,idx*2+1,l,x);
    }
    return res;
}

int hi(int s, int e, int idx, int l, int x){
    if(e < l)return -1;
    if(s == e){
        assert(mx[mt][idx] > x);
        return s;
    }

    int mid = (s+e)/2;
    int res = -1;
    if(mx[mt][idx*2] > x){
        res = hi(s,mid,idx*2,l,x);
    }

    if(res == -1 && mx[mt][idx*2+1] > x){
        res = hi(mid+1,e,idx*2+1,l,x);
    }
    return res;
}


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) {

    //arr.resize(N);
    a.assign(N,vector<int>());
    
    int q = S.size();
    int m = X.size();

    int i,k;

    for(i=0;i<m;i++){
        int x = X[i], y = Y[i];
        a[x].push_back(y);
        a[y].push_back(x);
    }

    int x = -1;
    for(i=0;i<N;i++){
        if(a[i].size() == 1)x = i;
    }
    assert(x != -1);
    assert(mt == false);
    
    arr[mt][0] = x;
    int y = x;
    x = a[x][0];
    for(i=1;i<N-1;i++){
        arr[mt][i] = x;
        if(a[x][0] == y){
            y = x;
            x = a[x][1];
        }
        else{
            y = x;
            x = a[x][0];
        }
    }
    arr[mt][N-1] = x;
    assert(a[x].size()==1);

    for(i=0;i<N;i++){
        arr[mt^1][i] = arr[mt][N-i-1];
        posi[arr[mt][i]] = i;
    }
    vector<int> ans;

    buildmx(0,N-1,1);
    buildmn(0,N-1,1);

    mt ^= 1;
    //reverse(all(arr));

    buildmx(0,N-1,1);
    buildmn(0,N-1,1);

    mt ^= 1;
    //reverse(all(arr));
    

    for(k=0;k<q;k++){
        int s = S[k], e = E[k];
        int l = L[k];
        int r = R[k];

        if(posi[s] < posi[e])
            mt = true;
        else
            mt = false;
       
       
        int idx = lo(0,N-1,1,s,l);
        
        if(idx == -1 || idx > e){
            ans.push_back(true);
            continue;
        }

        if(arr[mt][idx-1] > r){
            ans.push_back(false);
            continue;
        }

        idx = hi(0,N-1,1,idx,r);

        if(idx == -1 || idx > e){
            ans.push_back(true);
//           continue;
        }
        else{
            ans.push_back(false);
        }

    }


    return ans;
}

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