제출 #152705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152705		Segtree	늑대인간 (IOI18_werewolf)	C++14	34 / 100	1337 ms	39920 KiB

werewolf

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define NN 200010
vector<ll> g[200010];
namespace segmi{
  ll dat[2*NN];
  void init(){
    for(int i=0;i<2*NN;i++)dat[i]=1e17;
  }
  void upd(ll i,ll x){
    i+=NN; dat[i]=x;
    for(;i;i>>=1){
      dat[i/2]=min(dat[i],dat[i^1]);
    }
  }
  ll qry(ll l,ll r){
    l+=NN,r+=NN+1;
    ll res=1e17;
    for(ll a=l,b=r;a<b;a>>=1,b>>=1){
      if(a&1)chmin(res,dat[a++]);
      if(b&1)chmin(res,dat[--b]);
    }
    return res;
  }
};
namespace segma{
  ll dat[2*NN];
  void init(){
    for(int i=0;i<2*NN;i++)dat[i]=-1e17;
  }
  void upd(ll i,ll x){
    i+=NN; dat[i]=x;
    for(;i;i>>=1){
      dat[i/2]=max(dat[i],dat[i^1]);
    }
  }
  ll qry(ll l,ll r){
    l+=NN,r+=NN+1;
    ll res=-1e17;
    for(ll a=l,b=r;a<b;a>>=1,b>>=1){
      if(a&1)chmax(res,dat[a++]);
      if(b&1)chmax(res,dat[--b]);
    }
    return res;
  }
};
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
    for(int i=0;i<X.size();i++){
	g[X[i]].push_back(Y[i]);
	g[Y[i]].push_back(X[i]);
    }
    ll arr[200010],id[200010];
    ll st,nex;
    for(int i=0;i<N;i++)if(g[i].size()==1)st=i;
    arr[0]=st;
    nex=g[st][0];
    for(int i=1;i<N;i++){
      arr[i]=nex;
      if(g[nex][0]==arr[i-1]){
	nex=g[nex][1];
      }
      else{
	nex=g[nex][0];
      }
    }
    for(int i=0;i<N;i++)id[arr[i]]=i;
    segmi::init(); for(int i=0;i<N;i++)segmi::upd(i,arr[i]);
    segma::init(); for(int i=0;i<N;i++)segma::upd(i,arr[i]);
    
    vector<int> ans;
    for(int q=0;q<S.size();q++){
        ans.push_back(0);
        ll l,r,mid;
	if(id[S[q]]<id[E[q]]){
	  l=id[S[q]],r=N;
	  while(l<r-1){
	    mid=(l+r)>>1;
	    if(segmi::qry(id[S[q]],mid)>=L[q])l=mid;
	    else r=mid;
	  }
	  ll vs=l;
	  
	  l=-1,r=id[E[q]];
	  while(l<r-1){
	    mid=(l+r)>>1;
	    if(segma::qry(mid,id[E[q]])<=R[q])r=mid;
	    else l=mid;
	  }
	  ll ve=r;
	  
	  ans[q]=(vs>=ve);
	}
	else{
	  l=-1,r=id[S[q]];
	  while(l<r-1){
	    mid=(l+r)>>1;
	    if(segmi::qry(mid,id[S[q]])>=L[q])r=mid;
	    else l=mid;
	  }
	  ll vs=r;
	  
	  l=id[E[q]],r=N;
	  while(l<r-1){
	    mid=(l+r)>>1;
	    if(segma::qry(id[E[q]],mid)<=R[q])l=mid;
	    else r=mid;
	  }
	  ll ve=l;
	  
	  ans[q]=(vs<=ve);
	}
    }
    return ans;
}/*
int main(){
  
  return 0;
}*/

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<X.size();i++){
                 ~^~~~~~~~~
werewolf.cpp:77:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int q=0;q<S.size();q++){
                 ~^~~~~~~~~
werewolf.cpp:61:11: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
     arr[0]=st;
     ~~~~~~^~~

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