Submission #155899

#TimeUsernameProblemLanguageResultExecution timeMemory
155899imyujinWerewolf (IOI18_werewolf)C++17
15 / 100
4106 ms90504 KiB
#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(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 z; 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; } 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; } x = dn[x]; while(x > 0 && e[z][x - 1] >= L) x--; return x; } int grb(int x, int L) { //return N - 2 - segr.gseg(1, 0, N - 2, N - dn[x] - 2, L); } x = dn[x]; while(x < N - 1 && e[z][x] >= L) x++; return x; } } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...