제출 #842369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842369		qin	늑대인간 (IOI18_werewolf)	C++17	34 / 100	581 ms	136700 KiB

werewolf

#ifdef LOCAL
#else
#include <werewolf.h>
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pli;
typedef double db;
typedef long double ldb;
struct st_query{
		int s, e, l, r, i;
		st_query(){}
		st_query(int S, int E, int L, int R) : s(S), e(E), l(L), r(R) {}
};
struct DSU{
		int c;
		vector<int> rep;
		void init(int n, int N){ c = N, rep = vector<int>(), rep.resize(n+1); for(int i = 1; i <= n; ++i) rep[i] = i; }
		int Find(int x){
				int b;
				if(x != rep[x]) b = x, x = Find(rep[x]), rep[b] = x;
				return x; 
		} void add_edge(int u, int v, vector<vector<int>> &g){
				u = Find(u), v = Find(v);
				if(u == v) return;
				g[++c].emplace_back(u), g[c].emplace_back(v);
				rep[u] = c, rep[v] = c;
		}
} DSU;
void dfs(int x, int &c, vector<vector<int>> &g, vector<pii> &preorder){
		++c, preorder[x].fi = c;
		for(int u : g[x]) dfs(u, c, g, preorder);
		preorder[x].se = c;
} struct st_event{
		int type; // 0 - poczatek -> query / 1 - punkt -> add / 2 - koniec -> query
		int l, r, i;
		st_event(){}
		st_event(int L) : type(1), l(L) {}
		st_event(int T, int L, int R, int I) : type(T), l(L), r(R), i(I) {}
		bool operator <(const st_event &x) { return type < x.type; }
}; int base = 1;
struct seg{
		vector<int> t;
		void init(int n){
				while(base < n) base <<= 1;
				t.resize(base<<1);
		} void add(int x){for(x += base-1; x; x >>= 1) ++t[x];}
		int query(int i, int pocz, int kon, int x, int y){
				if(x <= pocz && kon <= y) return t[i];
				int sr = (pocz+kon)>>1, wynik = 0;
				if(x <= sr) wynik += query(i<<1, pocz, sr, x, y);
				if(sr < y) wynik += query(i<<1|1, sr+1, kon, x, y);
				return wynik;
		}
} seg;
#ifdef LOCAL
int main(){
		int n, m, q, a, b; scanf("%d%d%d", &n, &m, &q);
		vector<vector<int>> g_greater(n+1), g_smaller(n+1);
		vector<st_query> v_query(q);
		vector<vector<pii>> starts(n+1), ends(n+1);
		for(int i = 0; i < m; ++i){
				scanf("%d%d", &a, &b); ++a, ++b;
				if(a > b) swap(a, b);
				g_greater[a].emplace_back(b), g_smaller[b].emplace_back(a);
		} for(int i = 0; i < q; ++i){
				scanf("%d%d%d%d", &v_query[i].s, &v_query[i].e, &v_query[i].l, &v_query[i].r);
				++v_query[i].s, ++v_query[i].e, ++v_query[i].l, ++v_query[i].r, v_query[i].i = i;
				starts[v_query[i].l].emplace_back(v_query[i].s, i), ends[v_query[i].r].emplace_back(v_query[i].e, i);
		} vector<vector<int>> gL(n+m+1), gR(n+m+1);
		vector<int> query_nodes_L(q), query_nodes_R(q);
		vector<pii> preorderL(n+m+1), preorderR(n+m+1);
		//tworzenie pierwszego drzewa (dla L)
		DSU.init(n+m, n);
		for(int x = n-1; x; --x){
				for(int u : g_greater[x]) DSU.add_edge(x, u, gL);
				for(pii s : starts[x]) query_nodes_L[s.se] = DSU.Find(s.fi);
		} int cnt = 0; dfs(DSU.c, cnt, gL, preorderL);
		//tworzenie drugiego drzewa (dla R)
		DSU.init(n+m, n);
		for(int x = 2; x <= n; ++x){
				for(int u : g_smaller[x]) DSU.add_edge(x, u, gR);
				for(pii s : ends[x]) query_nodes_R[s.se] = DSU.Find(s.fi);
		} cnt = 0; dfs(DSU.c, cnt, gR, preorderR);
		//tworzenie zamiatania
		seg.init(n+m+1);
		vector<vector<st_event>> t(n+m+1);
		for(int i = 0; i < q; ++i)
				t[preorderL[query_nodes_L[i]].fi].emplace_back(0, preorderR[query_nodes_R[i]].fi, preorderR[query_nodes_R[i]].se, i),
				t[preorderL[query_nodes_L[i]].se].emplace_back(2, preorderR[query_nodes_R[i]].fi, preorderR[query_nodes_R[i]].se, i);
		for(int i = 1; i <= n; ++i) t[preorderL[i].fi].emplace_back(preorderR[i].fi);
		vector<int> wynik(q);
		for(int i = 1; i <= n+m; ++i){
				sort(t[i].begin(), t[i].end());
				for(st_event u : t[i]){
						if(!u.type) wynik[u.i] = seg.query(1, 1, base, u.l, u.r);
						else if(u.type == 2) wynik[u.i] = min(1, seg.query(1, 1, base, u.l, u.r) - wynik[u.i]);
						else seg.add(u.l);
				}
		} for(int i : wynik) printf("%d\n", i);
		return 0;
}
#else
vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
		int m = ssize(X), q = ssize(S), a, b;
		vector<vector<int>> g_greater(n+1), g_smaller(n+1);
		vector<st_query> v_query(q);
		vector<vector<pii>> starts(n+1), ends(n+1);
		for(int i = 0; i < m; ++i){
				a = X[i], b = Y[i], ++a, ++b;
				if(a > b) swap(a, b);
				g_greater[a].emplace_back(b), g_smaller[b].emplace_back(a);
		} for(int i = 0; i < q; ++i){
				v_query[i].s = S[i], v_query[i].e = E[i], v_query[i].l = L[i], v_query[i].r = R[i];
				++v_query[i].s, ++v_query[i].e, ++v_query[i].l, ++v_query[i].r, v_query[i].i = i;
				starts[v_query[i].l].emplace_back(v_query[i].s, i), ends[v_query[i].r].emplace_back(v_query[i].e, i);
		} vector<vector<int>> gL(n+m+1), gR(n+m+1);
		vector<int> query_nodes_L(q), query_nodes_R(q);
		vector<pii> preorderL(n+m+1), preorderR(n+m+1);
		//tworzenie pierwszego drzewa (dla L)
		DSU.init(n+m, n);
		for(int x = n-1; x; --x){
				for(int u : g_greater[x]) DSU.add_edge(x, u, gL);
				for(pii s : starts[x]) query_nodes_L[s.se] = DSU.Find(s.fi);
		} int cnt = 0; dfs(DSU.c, cnt, gL, preorderL);
		//tworzenie drugiego drzewa (dla R)
		DSU.init(n+m, n);
		for(int x = 2; x <= n; ++x){
				for(int u : g_smaller[x]) DSU.add_edge(x, u, gR);
				for(pii s : ends[x]) query_nodes_R[s.se] = DSU.Find(s.fi);
		} cnt = 0; dfs(DSU.c, cnt, gR, preorderR);
		//tworzenie zamiatania
		seg.init(n+m+1);
		vector<vector<st_event>> t(n+m+1);
		for(int i = 0; i < q; ++i)
				t[preorderL[query_nodes_L[i]].fi].emplace_back(0, preorderR[query_nodes_R[i]].fi, preorderR[query_nodes_R[i]].se, i),
				t[preorderL[query_nodes_L[i]].se].emplace_back(2, preorderR[query_nodes_R[i]].fi, preorderR[query_nodes_R[i]].se, i);
		for(int i = 1; i <= n; ++i) t[preorderL[i].fi].emplace_back(preorderR[i].fi);
		vector<int> wynik(q);
		for(int i = 1; i <= n+m; ++i){
				sort(t[i].begin(), t[i].end());
				for(st_event u : t[i]){
						if(!u.type) wynik[u.i] = seg.query(1, 1, base, u.l, u.r);
						else if(u.type == 2) wynik[u.i] = min(1, seg.query(1, 1, base, u.l, u.r) - wynik[u.i]);
						else seg.add(u.l);
				}
		}
		return wynik;
} 
#endif

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