// this code is bugged
#include "werewolf.h"
#include <bits/stdc++.h>
#define int long long
#define sz(x) ((x).size())
#define mp pair<pii, pii>
#define pii pair<int, int>
#define f first
#define s second
using namespace std;
const int inf = 1e9;
const int p2 = 1<<18;
const int siz = 4e5+40;
const int LG = 20;
struct Segtree {
Segtree() {
t = new int [p2*2];
cls();
}
~Segtree() {
delete [] t;
}
void cls() {
for (int i = 0; i < p2*2; i++) t[i] = 0;
}
void upd(int x, int v) {
for (x += p2; x; x /= 2) {
t[x] += v;
}
}
int get(int b, int e) {
int r = 0;
b += p2;
e += p2;
while (b <= e) {
if (b%2 == 1) {
r += t[b];
b++;
}
if (e%2 == 0) {
r += t[e];
e--;
}
b /= 2;
e /= 2;
}
return r;
}
int* t;
};
vector<int> order [2];
vector<int> graph [2][siz];
vector<int> ett [2];
int posOfInEtt [2][siz];
int dsu [siz];
int jmp [2][siz][LG];
int smallerP2 [siz];
vector<int> posInOne [siz];
int gp(int x) {
if (dsu[x] == x) return x;
return dsu[x] = gp(dsu[x]);
}
bool merge(int x, int y) {
x = gp(x);
y = gp(y);
if (x == y) return false;
dsu[y] = x;
return true;
}
void dfs(int T, int x, int p = -1) {
ett[T].push_back(x);
for (int y : graph[T][x]) if (y != p) {
dfs(T, y, x);
ett[T].push_back(x);
}
}
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
int getMinZero(int start, int end) {
int power = smallerP2[end-start+1];
return min(jmp[0][start][power], jmp[0][end-(1<<power)+1][power]);
}
int getMaxOne(int start, int end) {
int power = smallerP2[end-start+1];
return max(jmp[1][start][power], jmp[1][end-(1<<power)+1][power]);
}
std::vector<signed> check_validity(const signed n, std::vector<signed> edgeX, std::vector<signed> edgeY, std::vector<signed> queryX, std::vector<signed> queryY, std::vector<signed> queryLB, std::vector<signed> queryRB) {
for (int i = 0; i < siz; i++) {
smallerP2[i] = 0;
while ((1<<(smallerP2[i]+1)) <= i) {
smallerP2[i]++;
}
}
vector<int> adj [n];
for (int i = 0; i < sz(edgeX); i++) {
adj[edgeX[i]].push_back(edgeY[i]);
adj[edgeY[i]].push_back(edgeX[i]);
}
typedef int (*CompFunct) (int a, int b);
CompFunct funct [2] = {min, max};
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) order[i].push_back(j);
if (i == 1) reverse(order[i].begin(), order[i].end());
for (int j = 0; j < n; j++) dsu[j] = j;
bool seen [n];
for (int j = 0; j < n; j++) seen[j] = false;
for (int jIdx = n-1; jIdx >= 0; jIdx--) {
int j = order[i][jIdx];
for (int k : adj[j]) if (seen[k]) {
int pJ = gp(j);
int pK = gp(k);
if (pJ != pK) {
graph[i][pJ].push_back(pK);
graph[i][pK].push_back(pJ);
assert(merge(pJ, pK));
}
}
seen[j] = true;
}
dfs(i, order[i][0]);
assert(sz(ett[i]) == 2*n-1);
for (int j = 0; j < 2*n-1; j++) {
posOfInEtt[i][ett[i][j]] = j;
}
for (int j = 0; j < 2*n-1; j++) jmp[i][j][0] = ett[i][j];
for (int j = 1; j < LG; j++) {
for (int k = 0; k < 2*n-1; k++) {
if (k+(1<<(j-1)) >= 2*n-1) {
jmp[i][k][j] = jmp[i][k][j-1];
}
else {
jmp[i][k][j] = funct[i](jmp[i][k][j-1], jmp[i][k+(1<<(j-1))][j-1]);
}
}
}
}
const int nbQ = sz(queryX);
pii range [nbQ][2];
for (int i = 0; i < nbQ; i++) {
range[i][0] = {posOfInEtt[0][queryX[i]], posOfInEtt[0][queryX[i]]};
for (int j = p2; j; j /= 2) {
int prop = range[i][0].f-j;
if (prop < 0) continue;
if (getMinZero(prop, range[i][0].s) >= queryLB[i]) {
range[i][0].f = prop;
}
}
for (int j = p2; j; j /= 2) {
int prop = range[i][0].s+j;
if (prop >= 2*n-1) continue;
if (getMinZero(range[i][0].f, prop) >= queryLB[i]) {
range[i][0].s = prop;
}
}
}
for (int i = 0; i < nbQ; i++) {
range[i][1] = {posOfInEtt[1][queryY[i]], posOfInEtt[1][queryY[i]]};
for (int j = p2; j; j /= 2) {
int prop = range[i][1].f-j;
if (prop < 0) continue;
if (getMaxOne(prop, range[i][1].s) <= queryRB[i]) {
range[i][1].f = prop;
}
}
for (int j = p2; j; j /= 2) {
int prop = range[i][1].s+j;
if (prop >= 2*n-1) continue;
if (getMaxOne(range[i][1].f, prop) <= queryRB[i]) {
range[i][1].s = prop;
}
}
}
vector<mp> qAt [n*2-1];
for (int i = 0; i < nbQ; i++) {
qAt[range[i][0].s].push_back({range[i][1], {i, 1}});
if (range[i][0].f-1 >= 0) {
qAt[range[i][0].f-1].push_back({range[i][1], {i, -1}});
}
}
int cnt [nbQ];
for (int i = 0; i < nbQ; i++) cnt[i] = 0;
Segtree st = Segtree();
for (int i = 0; i < 2*n-1; i++) {
posInOne[ett[1][i]].push_back(i);
}
for (int i = 0; i < 2*n-1; i++) {
for (int j : posInOne[ett[0][i]]) {
st.upd(j, 1);
}
for (mp j : qAt[i]) {
cnt[j.s.f] += j.s.s*st.get(j.f.f, j.f.s);
}
}
vector<signed> res(nbQ, 0);
for (int i = 0; i < nbQ; i++) {
if (cnt[i] >= 1) {
res[i] = 1;
}
}
return res;
}
Compilation message
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:115:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int i = 0; i < sz(edgeX); i++) {
| ^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from werewolf.cpp:4:
werewolf.cpp:141:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
141 | assert(sz(ett[i]) == 2*n-1);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
35796 KB |
Output is correct |
| 2 |
Correct |
20 ms |
35796 KB |
Output is correct |
| 3 |
Correct |
22 ms |
35788 KB |
Output is correct |
| 4 |
Correct |
25 ms |
35668 KB |
Output is correct |
| 5 |
Correct |
23 ms |
35780 KB |
Output is correct |
| 6 |
Correct |
27 ms |
35792 KB |
Output is correct |
| 7 |
Correct |
26 ms |
35796 KB |
Output is correct |
| 8 |
Correct |
21 ms |
35864 KB |
Output is correct |
| 9 |
Correct |
21 ms |
35796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
35796 KB |
Output is correct |
| 2 |
Correct |
20 ms |
35796 KB |
Output is correct |
| 3 |
Correct |
22 ms |
35788 KB |
Output is correct |
| 4 |
Correct |
25 ms |
35668 KB |
Output is correct |
| 5 |
Correct |
23 ms |
35780 KB |
Output is correct |
| 6 |
Correct |
27 ms |
35792 KB |
Output is correct |
| 7 |
Correct |
26 ms |
35796 KB |
Output is correct |
| 8 |
Correct |
21 ms |
35864 KB |
Output is correct |
| 9 |
Correct |
21 ms |
35796 KB |
Output is correct |
| 10 |
Correct |
28 ms |
38936 KB |
Output is correct |
| 11 |
Correct |
28 ms |
38976 KB |
Output is correct |
| 12 |
Correct |
29 ms |
39004 KB |
Output is correct |
| 13 |
Correct |
29 ms |
38984 KB |
Output is correct |
| 14 |
Correct |
35 ms |
38984 KB |
Output is correct |
| 15 |
Correct |
30 ms |
39092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1475 ms |
486728 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
35796 KB |
Output is correct |
| 2 |
Correct |
20 ms |
35796 KB |
Output is correct |
| 3 |
Correct |
22 ms |
35788 KB |
Output is correct |
| 4 |
Correct |
25 ms |
35668 KB |
Output is correct |
| 5 |
Correct |
23 ms |
35780 KB |
Output is correct |
| 6 |
Correct |
27 ms |
35792 KB |
Output is correct |
| 7 |
Correct |
26 ms |
35796 KB |
Output is correct |
| 8 |
Correct |
21 ms |
35864 KB |
Output is correct |
| 9 |
Correct |
21 ms |
35796 KB |
Output is correct |
| 10 |
Correct |
28 ms |
38936 KB |
Output is correct |
| 11 |
Correct |
28 ms |
38976 KB |
Output is correct |
| 12 |
Correct |
29 ms |
39004 KB |
Output is correct |
| 13 |
Correct |
29 ms |
38984 KB |
Output is correct |
| 14 |
Correct |
35 ms |
38984 KB |
Output is correct |
| 15 |
Correct |
30 ms |
39092 KB |
Output is correct |
| 16 |
Runtime error |
1475 ms |
486728 KB |
Execution killed with signal 11 |
| 17 |
Halted |
0 ms |
0 KB |
- |
