Submission #121994

#	Time	Username	Problem	Language	Result	Execution time	Memory
121994		SirCeness	Werewolf (IOI18_werewolf)	C++14	34 / 100	1697 ms	26360 KiB

werewolf

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;

int arr[200005];
int ters[200005];
int komsu[2][200005];
int minst[800005];
int maxst[800005];
int n;

void minstc(int node, int l, int r){
	if (l == r) minst[node] = arr[l];
	else {
		int m = (l+r)/2;
		minstc(node*2, l, m);
		minstc(node*2+1, m+1, r);
		minst[node] = min(minst[node*2], minst[node*2+1]);
	}
}

int minstq(int node, int l, int r, int sl, int sr){
	if (sl <= l && r <= sr) return minst[node];
	else if (r < sl || sr < l) return 1000000000;
	else {
		int m = (l+r)/2;
		return min(minstq(node*2, l, m, sl, sr), minstq(node*2+1, m+1, r, sl, sr));
	}
}

void maxstc(int node, int l, int r){
	if (l == r) maxst[node] = arr[l];
	else {
		int m = (l+r)/2;
		maxstc(node*2, l, m);
		maxstc(node*2+1, m+1, r);
		maxst[node] = max(maxst[node*2], maxst[node*2+1]);
	}
}

int maxstq(int node, int l, int r, int sl, int sr){
	if (sl <= l && r <= sr) return maxst[node];
	else if (r < sl || sr < l) return -1000000000;
	else {
		int m = (l+r)/2;
		return max(maxstq(node*2, l, m, sl, sr), maxstq(node*2+1, m+1, r, sl, sr));
	}
}

int solve(int s, int e, int L, int R){
	if (s < e){
		int l = s;
		int r = e;
		while (l < r){
			int m = (l+r+1)/2;
			if (minstq(1, 0, n-1, l, m) < L) r = m-1;
			else l = m;
		}
		if (minstq(1, 0, n-1, s, l) >= L && maxstq(1, 0, n-1, l, e) <= R) return 1;
		else return 0;
	} else {
		int l = e;
		int r = s;
		while (l<r){
			int m = (l+r)/2;
			if (minstq(1, 0, n-1, m, r) < L) l = m+1;
			else r = m;
		}
		if (minstq(1, 0, n-1, l, s) >= L && maxstq(1, 0, n-1, e, l) <= R) return 1;
		else return 0;
	}
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	n = N;
	for (int i = 0; i < N; i++) komsu[0][i] = komsu[1][i] = -1;
	for (int i = 0; i < X.size(); i++){
		if (komsu[0][X[i]] == -1) komsu[0][X[i]] = Y[i];
		else komsu[1][X[i]] = Y[i];
		if (komsu[0][Y[i]] == -1) komsu[0][Y[i]] = X[i];
		else komsu[1][Y[i]] = X[i];
	}
	int basnode;
	for (basnode = 0; basnode < N; basnode++) if(komsu[1][basnode] == -1) break;
	arr[0] = basnode; ters[basnode] = 0;
	arr[1] = komsu[0][basnode]; ters[komsu[0][basnode]] = 1;
	for (int i = 2; i < N; i++){
		if (arr[i-2] != komsu[0][arr[i-1]] && komsu[0][arr[i-1]] != -1) arr[i] = komsu[0][arr[i-1]], ters[komsu[0][arr[i-1]]] = i;
		else arr[i] = komsu[1][arr[i-1]], ters[komsu[1][arr[i-1]]] = i;
	}
	
	//for (int i = 0; i < N; i++) cout << arr[i] << " "; cout << endl;
	
	vector<int> ans(S.size(), 5);
	minstc(1, 0, n-1);
	maxstc(1, 0, n-1);
	
	for (int i = 0; i < S.size(); i++) ans[i] = solve(ters[S[i]], ters[E[i]], L[i], R[i]);
	
	return ans;
}

Compilation message (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:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X.size(); i++){
                  ~~^~~~~~~~~~
werewolf.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) ans[i] = solve(ters[S[i]], ters[E[i]], L[i], R[i]);
                  ~~^~~~~~~~~~

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