#include "werewolf.h"
#include <bits/stdc++.h>
#define sz(x) ((x).size())
#define pii pair<int, int>
#define f first
#define s second
using namespace std;
const int inf = 1e9;
const int p2 = 1<<18;
struct Segtree {
Segtree() {
t = new int [p2*2];
cls();
}
~Segtree() {
delete [] t;
}
void cls() {
for (int i = 0; i < p2*2; i++) t[i] = -inf;
}
void upd(int x, int v) {
for (x += p2; x; x /= 2) {
t[x] = max(t[x], v);
}
}
int get(int b, int e) {
int r = -inf;
b += p2;
e += p2;
while (b <= e) {
if (b%2 == 1) {
r = max(r, t[b]);
b++;
}
if (e%2 == 0) {
r = max(r, t[e]);
e--;
}
b /= 2;
e /= 2;
}
return r;
}
int* t;
};
std::vector<int> check_validity(const int n, std::vector<int> edgeX, std::vector<int> edgeY, std::vector<int> queryX, std::vector<int> queryY, std::vector<int> queryLB, std::vector<int> queryRB) {
vector<int> graph [n];
for (int i = 0; i < sz(edgeX); i++) {
graph[edgeX[i]].push_back(edgeY[i]);
graph[edgeY[i]].push_back(edgeX[i]);
}
vector<int> path;
for (int i = 0; i < n; i++) if (sz(graph[i]) == 1) {
bool vis [n];
for (int j = 0; j < n; j++) vis[j] = false;
int x = i;
while (1) {
vis[x] = true;
path.push_back(x);
bool ch = false;
for (int y : graph[x]) if (!vis[y]) {
x = y;
ch = true;
break;
}
if (!ch) {
break;
}
}
break;
}
assert(sz(path) == n);
// path = {5, 0, 3, 1, 4, 2};
int invPath [n];
for (int i = 0; i < n; i++) invPath[path[i]] = i;
const int nbQ = sz(queryX);
for (int i = 0; i < nbQ; i++) {
queryX[i] = invPath[queryX[i]];
queryY[i] = invPath[queryY[i]];
}
vector<int> queryAt [n];
for (int i = 0; i < nbQ; i++) {
queryAt[queryRB[i]].push_back(i);
}
pii rangeX [nbQ];
Segtree MaxSegtree = Segtree();
Segtree MinSegtree = Segtree();
for (int i = n-1; i >= 0; i--) {
for (int j : queryAt[i]) {
rangeX[j].f = MaxSegtree.get(0, queryX[j])+1;
rangeX[j].s = -MinSegtree.get(queryX[j], n-1)-1;
}
MaxSegtree.upd(invPath[i], invPath[i]);
MinSegtree.upd(invPath[i], -invPath[i]);
}
MaxSegtree.cls();
MinSegtree.cls();
for (int i = 0; i < n; i++) queryAt[i].clear();
for (int i = 0; i < nbQ; i++) {
queryAt[queryLB[i]].push_back(i);
}
pii rangeY [nbQ];
for (int i = 0; i < n; i++) {
for (int j : queryAt[i]) {
rangeY[j].f = MaxSegtree.get(0, queryY[j])+1;
rangeY[j].s = -MinSegtree.get(queryY[j], n-1)-1;
}
MaxSegtree.upd(invPath[i], invPath[i]);
MinSegtree.upd(invPath[i], -invPath[i]);
}
vector<int> res(nbQ, 1);
for (int i = 0; i < nbQ; i++) {
if (rangeX[i].f > rangeX[i].s || rangeY[i].f > rangeY[i].s) {
res[i] = 0;
}
}
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:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | 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:2:
werewolf.cpp:78:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
78 | assert(sz(path) == n);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
433 ms |
40352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
