#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
struct segtree {
vector<int> T;
int get(int idx, int s, int e, int l, int r) {
if(r < s || e < l) return 0;
if(l <= s && e <= r) return T[idx];
int m = s+e >> 1;
return get(idx*2, s, m, l, r) + get(idx*2+1, m+1, e, l, r);
}
void upd(int idx, int s, int e, int p, int v) {
if(p < s || e < p) return;
if(s == e) {
T[idx] = v;
return;
}
int m = s+e >> 1;
upd(idx*2, s, m, p, v);
upd(idx*2+1, m+1, e, p, v);
T[idx] = T[idx*2] + T[idx*2+1];
}
segtree(int sz) { T.resize(4*sz); }
};
struct UF {
int P[400009], X[400009];
int root(int x) {
if(P[x] == x) return x;
return P[x] = root(P[x]);
}
pii merg(int u, int v, int Xi) {
u = root(u); v = root(v);
int a = X[u], b = X[v];
X[v] = X[u] = Xi;
P[u] = v;
return (pii){a, b};
}
UF(int sz) {
for(int i=0; i<sz; i++) P[i] = i, X[i] = i;
}
};
const int FF = 400009;
bool HVS[FF], WVS[FF];
int ans[FF], x[FF], ys[FF], ye[FF], C[FF], lineId[FF];
int Hw[FF], Ww[FF], HP[22][FF], WP[22][FF], l, Hi[FF], Ho[FF], Wi[FF], Wo[FF], Ht = 1, Wt = 1;
vector<int> adj[FF], HT[FF], WT[FF];
void WA() {
exit(0);
}
void Hdfs(int x, int p) {
Hi[x] = Ht;
if((int)HT[x].size() == 0) ++Ht;
HP[0][x] = p;
for(auto& it: HT[x]) Hdfs(it, x);
Ho[x] = Ht ;
}
void Wdfs(int x, int p) {
Wi[x] = Wt;
if((int)WT[x].size() == 0) ++Wt;
WP[0][x] = p;
for(auto& it: WT[x]) Wdfs(it, x);
Wo[x] = Wt ;
}
UF HUF(400001), WUF(400001);
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 = X.size(), Q = S.size();
for(int i=0; i<M; i++) {
int u = X[i], v = Y[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
int I = N - 1;
for(int i=N-1; i>=0; i--) {
for(auto& it: adj[i]) {
if(it < i) continue;
int u = i, v = it;
if(HUF.root(u) != HUF.root(v)) {
int a, b; tie(a, b) = HUF.merg(u, v, ++I);
HT[I].push_back(a);
HT[I].push_back(b);
Hw[I] = i;
}
}
}
Hdfs(I, I);
I = N - 1;
for(int i=0; i<N; i++) {
for(auto& it: adj[i]) {
if(it > i) continue;
int u = i, v = it;
if(WUF.root(u) != WUF.root(v)) {
int a, b; tie(a, b) = WUF.merg(u, v, ++I);
WT[I].push_back(a);
WT[I].push_back(b);
Ww[I] = i;
}
}
}
Wdfs(I, I);
/*
puts("DFS Ordering");
for(int i=0; i<N; i++) printf("%d ", Hi[i]);
puts("");
for(int i=0; i<N; i++) printf("%d ", Wi[i]);
puts("\n");
*/
for(int i=1; (1<<i)<=I; i++) {
for(int j=0; j<=I; j++) {
HP[i][j] = HP[i-1][HP[i-1][j]];
WP[i][j] = WP[i-1][WP[i-1][j]];
}
l = i;
}
vector<pii> evt;
for(int i=0; i<N; i++) evt.push_back({1, i});
int lineIdx = 0;
for(int i=0; i<Q; i++) {
int Hnow = S[i], Wnow = E[i];
for(int j=l; j>=0; j--) if(Hw[HP[j][Hnow]] >= L[i]) Hnow = HP[j][Hnow];
for(int j=l; j>=0; j--) if(Ww[WP[j][Wnow]] <= R[i]) Wnow = WP[j][Wnow];
x[++lineIdx] = Hi[Hnow] - 1; C[lineIdx] = -1;
ys[lineIdx] = Wi[Wnow]; ye[lineIdx] = Wo[Wnow];
lineId[lineIdx] = i;
evt.push_back({2, lineIdx});
x[++lineIdx] = Ho[Hnow]; C[lineIdx] = +1;
ys[lineIdx] = Wi[Wnow]; ye[lineIdx] = Wo[Wnow];
lineId[lineIdx] = i;
evt.push_back({2, lineIdx});
//printf("rectangle : (%d, %d, %d, %d)\n", Hi[Hnow], Wi[Wnow], Ho[Hnow], Wo[Wnow]);
}
sort(evt.begin(), evt.end(), [&](pii A, pii B) {
int Aty, Aid, Bty, Bid;
tie(Aty, Aid) = A; tie(Bty, Bid) = B;
int ax = (Aty == 1 ? Hi[Aid] : x[Aid]), bx = (Bty == 1 ? Hi[Bid] : x[Bid]);
if(ax == bx) return Aty < Bty;
return ax < bx;
});
segtree seg(N);
for(auto& it: evt) {
int ty, id; tie(ty, id) = it;
if(ty == 1) {
seg.upd(1, 1, N, Wi[id], 1);
//printf("dot update: vertex: %d, (%d, %d)\n", id, Hi[id], Wi[id]);
}
if(ty == 2) ans[lineId[id]] += C[id] * seg.get(1, 1, N, ys[id], ye[id]);
}
vector<int> A(Q, 0);
for(int i=0; i<Q; i++) if(ans[i]) A[i] = 1;
return A;
}
Compilation message
werewolf.cpp: In member function 'int segtree::get(int, int, int, int, int)':
werewolf.cpp:12:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | int m = s+e >> 1;
| ~^~
werewolf.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
werewolf.cpp:21:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | int m = s+e >> 1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
34888 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
34892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
34888 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
34892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1124 ms |
155928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
34888 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
34892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
