#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int N, M, Q;
vector<vector<int>> graph;
vector<int> human, wolf;
void makeArrays() {
human.clear();
wolf.clear();
{
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(0);
vector<bool> vis(N);
while (pq.size()) {
int v = pq.top();
pq.pop();
if (vis[v]) continue;
vis[v] = 1;
wolf.push_back(v);
for (int i: graph[v]) {
if (vis[i]) continue;
pq.push(i);
}
}
}
{
priority_queue<int> pq;
pq.push(N-1);
vector<bool> vis(N);
while (pq.size()) {
int v = pq.top();
pq.pop();
if (vis[v]) continue;
vis[v] = 1;
human.push_back(v);
for (int i: graph[v]) {
if (vis[i]) continue;
pq.push(i);
}
}
}
assert((int)human.size() == N && (int)wolf.size() == N);
}
vector<int> wolfInv, humanInv, humanToWolf;
void makeInv() {
wolfInv.resize(N);
humanInv.resize(N);
for (int i = 0; i<N; i++) wolfInv[wolf[i]] = i;
for (int i = 0; i<N; i++) humanInv[human[i]] = i;
humanToWolf.resize(N);
for (int i = 0; i<N; i++) humanToWolf[i] = wolfInv[human[i]];
}
struct seg {
struct node {
int val=0, left=-1, right=-1;
};
vector<node> tree = {node()};
void build(int v, int rl, int rr) {
if (rl == rr) return;
tree[v].left = tree.size();
tree.push_back(node());
tree[v].right = tree.size();
tree.push_back(node());
int rm = (rl + rr)/2;
build(tree[v].left, rl, rm);
build(tree[v].right, rm+1, rr);
}
int update(int v, int rl, int rr, int pos, int x) {
if (rl == rr) {
int newV = tree.size();
tree.push_back(tree[v]);
tree[newV].val += x;
return newV;
}
int rm = (rl + rr)/2;
int newV = tree.size();
tree.push_back(tree[v]);
if (pos <= rm) tree[newV].left = update(tree[newV].left, rl, rm, pos, x);
else tree[newV].right = update(tree[newV].right, rm+1, rr, pos, x);
tree[newV].val = tree[newV].left + tree[newV].right;
return newV;
}
int query(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return 0;
if (rl == ql && rr == qr) return tree[v].val;
int rm = (rl + rr)/2;
return query(tree[v].left, rl, rm, ql, min(qr, rm)) + query(tree[v].right, rm+1, rr, max(ql, rm+1), qr);
}
vector<int> times;
int queryDouble(int hl, int hr, int wl, int wr) {
return query(times[wr], 0, N-1, hl, hr) - (wl==0?0:query(times[wl-1], 0, N-1, hl, hr));
}
void init() {
build(0, 0, N-1);
for (int i = 0; i<N; i++) {
times.push_back(update(i==0?0:times.back(), 0, N-1, humanToWolf[i], 1));
}
assert((int)times.size() == N);
}
};
struct segSimple {
vector<pair<int, int>> tree;
pair<int, int> op(pair<int, int> a, pair<int, int> b) {
pair<int, int> res;
res.first = min(a.first, b.first);
res.second = max(a.second, b.second);
return res;
}
void update(int v, int rl, int rr, int pos, int x) {
if (rl == rr) {
tree[v] = {x, x};
return;
}
int rm = (rl + rr)/2;
if (pos <= rm) update(v*2, rl, rm, pos, x);
else update(v*2+1, rm+1, rr, pos, x);
tree[v] = op(tree[v*2], tree[v*2+1]);
}
pair<int, int> query(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return {1e9, -1e9};
if (ql == rl && qr == rr) return tree[v];
int rm = (rl + rr) / 2;
return op(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
}
void init(vector<int> a) {
tree.assign(N*4, {1e9, -1e9});
for (int i = 0; i<N; i++) {
update(1, 0, N-1, i, a[i]);
}
}
};
pair<int, int> getRangeHuman(segSimple s, int pos, int lim) {
pair<int, int> range;
{
int l = 0, r = pos;
while (l < r) {
int m = (l + r)/2;
if (s.query(1, 0, N-1, m, pos).first >= lim) r = m;
else l = m+1;
}
range.first = l;
}
{
int l = pos, r = N-1;
while (l < r) {
int m = (l + r + 1)/2;
// cerr << "q: " << pos << " " << m << " " << s.query(1, 0, N-1, pos, m).first << "\n";
if (s.query(1, 0, N-1, pos, m).first >= lim) l = m;
else r = m-1;
}
range.second = l;
}
return range;
}
pair<int, int> getRangeWolf(segSimple s, int pos, int lim) {
pair<int, int> range;
{
int l = 0, r = pos;
while (l < r) {
int m = (l + r)/2;
if (s.query(1, 0, N-1, m, pos).second <= lim) r = m;
else l = m+1;
}
range.first = l;
}
{
int l = pos, r = N-1;
while (l < r) {
int m = (l + r + 1)/2;
if (s.query(1, 0, N-1, pos, m).second <= lim) l = m;
else r = m-1;
}
range.second = l;
}
return range;
}
vector<int> check_validity(int _N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
N = _N;
M = X.size();
Q = S.size();
graph.resize(N);
for (int i = 0; i<M; i++) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
makeArrays();
makeInv();
seg tree;
tree.init();
segSimple humanSeg;
humanSeg.init(human);
segSimple wolfSeg;
wolfSeg.init(wolf);
// for (int i = 0; i<N; i++) {
// cerr << humanSeg.query(1, 0, N-1, i, i).first << " ";
// }
// cerr << "\n";
// for (int i: human) cerr << i << " ";
// cerr << "\n";
vector<int> res(Q, 0);
for (int i = 0; i<Q; i++) {
// cerr << humanInv[S[i]] << " " << L[i] << "\n";
pair<int, int> rangeHuman = getRangeHuman(humanSeg, humanInv[S[i]], L[i]);
pair<int, int> rangeWolf = getRangeWolf(wolfSeg, wolfInv[E[i]], R[i]);
// cerr << rangeHuman.first << " " << rangeHuman.second << " " << rangeWolf.first << " " << rangeWolf.second << "\n";
// cerr << tree.queryDouble(rangeHuman.first, rangeHuman.second, rangeWolf.first, rangeWolf.second) << "\n";
if (tree.queryDouble(rangeHuman.first, rangeHuman.second, rangeWolf.first, rangeWolf.second)) res[i] = 1;
}
// cerr << "\n---\n\n";
return res;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4093 ms |
102148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
