Submission #1105179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105179		thelegendary08	Werewolf (IOI18_werewolf)	C++14	49 / 100	1877 ms	69352 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<int>
using namespace std;
const int mxn = 200005;
int tree[mxn*4][2];
int n;
bool intersect(pair<int,int>a, pair<int,int>b){
	if(a.first > b.first)swap(a,b);
	if(a.first > a.second || b.first > b.second)return false;
	if(a.second < b.first)return false;
	else return true;
}
int quer(int l, int r, int d){
	l += n;
	r+=n;
	int s = 0;
	while(l<=r){
		if(l % 2 == 1)s += tree[l++][d];
		if(r % 2 == 0)s += tree[r--][d];
		l/=2;
		r/=2;
	}
	return s;
}
void upd(int k, int x, int d){
	k += n;
	tree[k][d] = x;
	for(k/=2; k>=1; k/=2){
		tree[k][d] = tree[k*2][d] + tree[k*2+1][d];
	}
}
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) {
	n = N;
  int Q = S.size();
  int m = X.size();
  vector<int>adj[N];
  f0r(i, m){
  	adj[X[i]].pb(Y[i]);
  	adj[Y[i]].pb(X[i]);
  }
  vector<int>ans(Q);
  //N <= 3000 && m <= 6000 && Q <= 3000
  if(N <= 3000 && m <= 6000 && Q <= 3000){
  	f0r(t, Q){
	  	int s = S[t];
	  	int e = E[t];
	  	int l = L[t];
	  	int r = R[t];
	  	vector<bool>vis(N, 0);
	  	vector<bool>wis(N, 0);
	  	
	  	queue<int>q;
	  	if(s >= l){
	  		vis[s] = 1;
	  		q.push(s);
	  	}
	  	while(!q.empty()){
	  		int node = q.front();
	  		q.pop();
	  		for(auto u : adj[node]){
	  			if(vis[u])continue;
	  			if(u < l)continue;
	  			vis[u] = 1;
	  			q.push(u);
	  		}
	  	}
	  	
	  	if(e <= r){
	  		wis[e] = 1;
	  		q.push(e);
	  	}
	  	while(!q.empty()){
	  		int node = q.front();
	  		q.pop();
	  		for(auto u : adj[node]){
	  			if(wis[u])continue;
	  			if(u > r)continue;
	  			wis[u] = 1;
	  			q.push(u);
	  		}
	  	}
	  	int a = 0;
	  	f0r(i,N){
	  		if(vis[i] && wis[i])a = 1;
	  	}
	  	ans[t] = a;
	  }
	  
	  return ans;
  }
  else{
  	int fi;
  	f0r(i,N){
  		if(adj[i].size() == 1)fi = i;
  	}
  	vi dex;
  	dex.pb(fi);
  	vector<bool>vis(N, 0);
  	vis[fi] = 1;
  	queue<int>q;
  	q.push(fi);
  	while(!q.empty()){
  		int node = q.front();
  		q.pop();
  		for(auto u : adj[node]){
  			if(vis[u])continue;
  			vis[u] = 1;
  			dex.pb(u);
  			q.push(u);
  		}
  	}
  	
  	vi invmap(N);
  	f0r(i, N){
  		invmap[dex[i]] = i;
  	}
  	vector<vi>lefts;
  	vector<vi>rights;
  	f0r(i, Q){
  		lefts.pb({L[i], invmap[S[i]], i});
  		rights.pb({R[i], invmap[E[i]], i});
  	}
  	sort(lefts.begin(), lefts.end());
  	sort(rights.rbegin(), rights.rend());
  	//for(auto u : invmap)cout<<u<<' ';
  	//cout<<'\n';
  	
  	f0r(i, n){
  		upd(i, 1, 0);
  		upd(i, 1, 1);
  	}
  	
  	int cur = -1;
  	vector<pair<int,pair<int,int>>>la;
  	vector<pair<int,pair<int,int>>>ra;
  	
  	f0r(i,Q){
  		if(lefts[i][0]-1 > cur){
  			for(int j = cur + 1; j <= lefts[i][0]-1; j++){
  				upd(invmap[j], 0, 0);
  			}
  			cur = lefts[i][0]-1;
  			
  			
  		}
  		f0r(j, n){
  			//cout<<tree[j+n][0]<<' ';
  		}
  		//cout<<'\n';
  		//f0r(j,3)cout<<lefts[i][j]<<' ';
  		//cout<<'\n';
  		//bs the first index in [l, N] to have a 0
  		int l = lefts[i][1];
  		int lo = l;
		int hi = N;
		//cout<<lo<<' '<<hi<<'\n';
		while(lo < hi){
			//cout<<lo<<' '<<hi<<'\n';
			int mid = lo + (hi - lo)/2;
			if(quer(l, mid, 0) < mid - l + 1){
				hi = mid;
			}
			else{
				lo = mid + 1;
			}
			
		}
		int lo2 = -1;
		int hi2 = l;
		while(lo2 < hi2){
			int mid = lo2 + (hi2 - lo2 + 1)/2;
			if(quer(mid, l, 0) < l - mid + 1){
				lo2 = mid;
			}
			else{
				hi2 = mid - 1;
			}
		}
		la.pb({lefts[i][2], {lo2+1, lo-1}});
  	}
  	
  	cur = N;
  	f0r(i,Q){
  		if(rights[i][0]+1 < cur){
  			for(int j = cur - 1; j >= rights[i][0]+1; j--){
  				upd(invmap[j], 0, 1);
  			}
  			cur = rights[i][0]+1;
  		}
  		//bs the last index in [-1, r] to have a 0
  		int r = rights[i][1];
  		int lo = -1;
		int hi = r;
		while(lo < hi){
			int mid = lo + (hi - lo + 1)/2;
			if(quer(mid, r, 1) < r - mid + 1){
				lo = mid;
			}
			else{
				hi = mid - 1;
			}
		}
		int lo2 = r;
		int hi2 = n;
		while(lo2 < hi2){
			int mid = lo2 + (hi2 - lo2)/2;
			if(quer(r, mid, 1) < mid - r + 1){
				hi2 = mid;
			}
			
			else{
				lo2 = mid + 1;
			}
		}
		ra.pb({rights[i][2], {lo+1, lo2-1}});
  	}
  	sort(la.begin(), la.end());
  	sort(ra.begin(), ra.end());
  	//for(auto u : la)cout<<u.second.first<<' '<<u.second.second<<' ';
  	//cout<<'\n';
  	//for(auto u : ra)cout<<u.second.first<<' '<<u.second.second<<' ';
  	//cout<<'\n';
  	vi ans(Q);
  	f0r(i, Q){
  		if(intersect(la[i].second, ra[i].second))ans[i] = 1;
  		else ans[i] = 0;
  	}
  	return ans;
  	
  	//return {};
  }
}

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