Submission #139199

#	Time	Username	Problem	Language	Result	Execution time	Memory
139199		rajarshi_basu	Werewolf (IOI18_werewolf)	C++14	34 / 100	839 ms	524288 KiB

werewolf

#include <bits/stdc++.h>

#include "werewolf.h"

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define vv vector
#define ii pair<int,int>

using namespace std;

const int MAXN = 2*100*1000 +1;
const int INF = 2*MAXN;
vi g[MAXN];
int n;

struct SegmentTree{
	int st[4*MAXN];
	int dp[4*MAXN];
	
	
	void build(int node,int ss,int se,int* arr){
		if(node == 0)FOR(i,n)dp[i] = arr[i];
		//return;
		
		
		if(ss == se){
			st[node] = arr[ss];
			return;
		}
		int mid = (ss+se)/2;
		build(node*2+1,ss,mid,arr);
		build(node*2+2,mid+1,se,arr);
		st[node] = min(st[node*2+1],st[node*2+2]);
	}
	int getLastValue(int node,int ss,int se,int bound,int val){
		/*se = bound;
		//se = min(se,bound);
		while(1){
			if(se == -1)break;
			if(st[se] < val)return se;
			se--;
		}
		return -1;*/
		
		
		if(ss > bound)return -1; 
		if(st[node] >= val)return -1;
		int mid = (ss+se)/2;
		if(ss == se)return ss;
		int vv = getLastValue(node*2+2,mid+1,se,bound,val);
		if(vv == -1)return getLastValue(node*2+1,ss,mid,bound,val);
		return vv;
	}
	int getFirstValue(int node,int ss,int se,int bound,int val){
		ss = bound;
		//ss = max(ss,bound);
		while(1){
			if(ss == n)break;
			if(dp[ss] < val)return ss;
			ss++;
		}
		return n;
		
		
		if(ss > bound)return -1; 
		if(st[node] >= val)return -1;
		int mid = (ss+se)/2;
		if(ss == se)return ss;
		int vv = getLastValue(node*2+2,mid+1,se,bound,val);
		if(vv == -1)return getLastValue(node*2+1,ss,mid,bound,val);
		return vv;
	}
};

SegmentTree human_normal,human_reverse,wolf_normal,wolf_reverse;


int place[MAXN];
int rplace[MAXN];

int T = 0;
void dfs(int node,int p = -1){
	place[node] = T;
	rplace[T] = node;
	T++;
	for(auto e : g[node]){
		if(e != p)dfs(e,node);
	}
}

bool solve(int n,int l,int r,int s,int e){
	s = place[s];
	e = place[e];
	ii p1;
	ii p2;
	p1.ff = human_normal.getLastValue(0,0,n-1,s,l)  + 1;// + 1;
	p1.ss = n - human_reverse.getLastValue(0,0,n-1,n-s-1,l) - 1 -1;//human_normal.getFirstValue(0,0,n-1,s,l) - 1;// - 1;//
	p2.ff = wolf_normal.getLastValue(0,0,n-1,e,-r)  + 1;// + 1;
	p2.ss =n - wolf_reverse.getLastValue(0,0,n-1,n-e-1,-r) - 1 -1;	// wolf_normal.getFirstValue(0,0,n-1,e,-r) - 1;// - 1;//
	//while(1);
	
	if(p1.ff == p2.ff)return true;
	if(p1.ff > p2.ff)swap(p1,p2);
	return p1.ss >= p2.ff; 
	
}

vi check_validity(int n,vi x,vi y,vi s,vi e,vi l,vi r){
	FOR(i,(int)x.size()){
		g[x[i]].pb(y[i]);
		g[y[i]].pb(x[i]);
	}
	::n = n;
	int q = s.size();
	vi ret;FOR(i,q)ret.pb(0);
	// preprocess stuff
	
	int root = 0;
	FOR(i,n)if(g[i].size() == 1)root = i;
	dfs(root);
	
	int arr[n];
	
	FOR(i,n)arr[i] = rplace[i];
	human_normal.build(0,0,n-1,arr);
	
	FOR(i,n)arr[i] = rplace[n-i-1];
	human_reverse.build(0,0,n-1,arr);
	
	FOR(i,n)arr[i] = -rplace[i];
	wolf_normal.build(0,0,n-1,arr);
	
	FOR(i,n)arr[i] = -rplace[n-i-1];
	wolf_reverse.build(0,0,n-1,arr);
	
	//////////////////////////////////
	FOR(i,q){
		ret[i] = solve(n,l[i],r[i],s[i],e[i]);
	}
	return ret;
}

int ma1in(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}

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