Submission #155901

#	Time	Username	Problem	Language	Result	Execution time	Memory
155901		imyujin	Werewolf (IOI18_werewolf)	C++17	100 / 100	881 ms	94620 KiB

werewolf

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

typedef pair<int, int> pii;

#define eb emplace_back
#define all(v) ((v).begin()),((v).end())
#define fi first
#define se second
#define rb(x) ((x)&(-(x)))

const int MAXN = 200010;
const int MX = 1 << 18;
int N;

struct SEG {
	int seg[2 * MX];

	void mkseg(int idx, int l, int r, vector<int> &e) {
		if(l == r) seg[idx] = e[l];
		else {
			int m = (l + r) / 2;
			mkseg(idx * 2, l, m, e);
			mkseg(idx * 2 + 1, m + 1, r, e);
			seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]);
		}
	}
	void init(vector<int> &e) { mkseg(1, 0, e.size() - 1, e); }

	int gseg(int idx, int l, int r, int x, int z) {
		if(x < l) return l - 1;
		//if(idx == 1) printf("gseg(x = %d, z = %d)\n", x, z);
		if(seg[idx] >= z) return l - 1;
		if(l == r) return l;
		int m = (l + r) / 2;
		if(x > m) {
			int t = gseg(idx * 2 + 1, m + 1, r, x, z);
			if(t > m) return t;
		}
		return gseg(idx * 2, l, m, x, z);
	}
};

struct TREE {
	vector<pii> ed;
	int uni[MAXN];
	vector<int> v[MAXN], e[MAXN];
	int dn[MAXN];
	SEG seg, segr;

	int guni(int x) { return uni[x] == x ? x : uni[x] = guni(uni[x]); }
	
	void init(vector<int> &X, vector<int> &Y) {
		int M = X.size();
		for(int i = 0; i < M; i++) ed.eb(min(X[i], Y[i]), max(X[i], Y[i]));
		sort(all(ed), greater<pii>());
		for(int i = 0; i < N; i++) {
			v[i].push_back(i);
			uni[i] = i;
		}
		//for(auto a : ed) printf("(%d, %d)", a.fi, a.se);
		//puts("");

		for(auto a : ed) {
			int x = guni(a.fi), y = guni(a.se);
			//printf("x = %d, y = %d\n", x, y);
			if(x == y) continue;
			if(v[x].size() < v[y].size()) swap(x, y);
			v[x].insert(v[x].end(), all(v[y]));
			e[x].push_back(a.fi);
			e[x].insert(e[x].end(), all(e[y]));
			uni[y] = x;
		}
		int z = guni(0);
		for(int i = 0; i < N; i++) dn[v[z][i]] = i;
		/*
		for(auto a : v[z]) printf("%d ", a);
		puts("");
		for(auto a : e[z]) printf("%d ", a);
		puts("");
		for(int i = 0; i < N; i++) printf("%d ", dn[i]);
		puts("");
		*/
		seg.init(e[z]);
		for(int i = 0; i < (N - 1) / 2; i++) swap(e[z][i], e[z][N - i - 2]);
		segr.init(e[z]);
	}

	int glb(int x, int L) { return seg.gseg(1, 0, N - 2, dn[x] - 1, L) + 1; }
	int grb(int x, int L) { return N - 2 - segr.gseg(1, 0, N - 2, N - dn[x] - 2, L); }
} hm, ww;

int dot[MAXN];
vector<int> qry[MAXN];
int u[MAXN], d[MAXN];
int bit[MAXN];

void updbit(int x) { for(x += 5; x < MAXN; x += rb(x)) bit[x]++; }
int gbit(int x) {
	int ans = 0;
	for(x += 5; x; x -= rb(x)) ans += bit[x];
	return ans;
}
int gbit(int x, int y) { return gbit(y) - gbit(x - 1); }

vector<int> check_validity(int NN, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	N = NN;
	int M = X.size(), Q = S.size();
	hm.init(X, Y);
	for(int i = 0; i < M; i++) {
		X[i] = N - 1 - X[i];
		Y[i] = N - 1 - Y[i];
	}
	ww.init(X, Y);

	for(int i = 0; i < N; i++) dot[hm.dn[i]] = ww.dn[N - i - 1];
	//for(int i = 0; i < Q; i++)
		//printf("%d %d %d %d\n", hm.glb(S[i], L[i]), hm.grb(S[i], L[i]), ww.glb(N - E[i] - 1, N - R[i] - 1), ww.grb(N - E[i] - 1, N - R[i] - 1));
	for(int i = 0; i < Q; i++) {
		int t = hm.glb(S[i], L[i]);
		if(t > 0) qry[t - 1].push_back(-i - 1);
		qry[hm.grb(S[i], L[i])].push_back(i);
		d[i] = ww.glb(N - E[i] - 1, N - R[i] - 1);
		u[i] = ww.grb(N - E[i] - 1, N - R[i] - 1);
	}

	vector<int> ans(Q, 0);
	for(int i = 0; i < N; i++) {
		updbit(dot[i]);
		for(auto a : qry[i]) {
			//printf("i = %d, a = %d\n", i, a);
			if(a >= 0) ans[a] += gbit(d[a], u[a]);
			else ans[-a - 1] -= gbit(d[-a - 1], u[-a - 1]);
		}
	}
	for(auto &a : ans) a = min(a, 1);
	return ans;
}

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