제출 #800232

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

werewolf

//#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

const int INF=1e9+7;

struct node{
    int maxi=0;
    int mini=INF;
};
node none={0, INF};

struct segtree{
    vector<node> tree;

    segtree(int n){
        tree.assign(n*4, none);
    }

    node merge(node a, node b){
        a.maxi = max(a.maxi, b.maxi);
        a.mini = min(a.mini, b.mini);
        return a;
    }

    node update(int l, int r, int v, int x, int val){
        if(x<l || r<=x) return tree[v];
        if(l+1==r){
            return tree[v]={val, val};
        }
        int m=l+(r-l)/2;
        return tree[v] = merge(update(l, m, v*2+1, x, val), update(m, r, v*2+2, x, val));
    }

    node query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return none;
        if(ql<=l && r<=qr){
            return tree[v];
        }
        int m=l+(r-l)/2;
        return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
};

bool line_query(int n, segtree& seg, int a, int b, int left, int right){

    int l=a; int r=b;
    int ans=-1;
    while(l<=r){
        int m=l+(r-l)/2;

        if(left <= seg.query(0, n, 0, a, m+1).mini){
            ans = m;
            l = m+1;
        }
        else{
            r=m-1;
        }
    }
    int lastr=ans;

    l=a;  r=b;
    ans=n;
    while(l<=r){
        int m=l+(r-l)/2;

        if(seg.query(0, n, 0, m, b+1).maxi <= right){
            ans = m;
            r = m-1;
        }
        else{
            l = m+1;
        }
    }
    int lastl=ans;

    return lastl <= lastr;
}

vector<int> solve_line(int n, vector<vector<int> >& adi, vector<int>& s, vector<int>& e,
                        vector<int>& l, vector<int>& r){

    //find line
    vector<int> line;
    int start=0;
    for(int v=0; v<n; v++){

        if(adi[v].size()==1){
            start=v;
        }
    }
 
    int v=start; int p=-1;
    for(int i=0; i<n; i++){

        line.push_back(v);

        for(auto u: adi[v]){

            if(u!=p){

                p=v;
                v=u;
                break;
            }
        }

    }

    vector<int> ind(n);
    for(int i=0; i<n; i++){
        ind[line[i]]=i;
    }

    //initialize segtree
    segtree seg(n);
    for(int i=0; i<n; i++){

        seg.update(0, n, 0, i, line[i]);
    }


    //answer queries
    int q=s.size();
    vector<int> ans(q);
    for(int i=0; i<q; i++){
        int a=ind[s[i]]; int b=ind[e[i]];


        ans[i] = line_query(n, seg, a, b, l[i], r[i]);
    }

    return ans;
}

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 m=x.size();

    vector<vector<int> > adi(n);
    for(int i=0; i<m; i++){
        adi[x[i]].push_back(y[i]);
        adi[y[i]].push_back(x[i]);
    }

    return solve_line(n, adi, s, e, l, r);
}

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