//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include "werewolf.h"
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(int x = 1 ; x <= (int)y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef pair<ll,ll> pll;
typedef complex<int> point;
const int nmax = 200005;
const ll linf = 1e18;
const ll mod = 998244353;
const int inf = 1e9+10;
const int sq = 5000;
int N;
struct {
int parent[nmax], size[nmax];
void init(int n){
for(int i = 1; i <= n;i++){
parent[i] = i;
size[i] = 1;
}
}
int par(int nod){
while(parent[nod] != parent[parent[nod]]){
parent[nod] = parent[parent[nod]];
}
return parent[nod];
}
bool same(int x , int y){
x = par(x);
y = par(y);
return x == y;
}
void conn(int x , int y){
x = par(x);
y = par(y);
if(size[x] < size[y])swap(x,y);
parent[y] = x;
size[x] += size[y];
}
} dsa, dsb;
vec < int > g1[nmax], g2[nmax];
vec <int> tour1, tour2, rev;
vec < pair < pii , pii > > lil_qs;
int la[nmax],lb[nmax],ra[nmax],rb[nmax];
int tim = 0;
void dfs1(int nod){
tim ++;
la[nod] = tim;
tour1.pb(nod);
for(int j : g1[nod]){
dfs1(j);
}
ra[nod] = tim;
}
void dfs2(int nod){
tim ++;
lb[nod] = tim;
tour2.pb(nod);
for(int j : g2[nod]){
dfs2(j);
}
rb[nod] = tim;
}
vec <int> result;
int bit[nmax];
void update(int pos){
for(;pos <= N; pos += pos&-pos){
bit[pos]++;
}
}
int query(int pos){
int rs = 0;
for(;pos > 0; pos -= pos&-pos){
rs += bit[pos];
}
return rs;
}
int prb[nmax][22] , pra[nmax][22];
vec <int> check_validity(int n,vec <int> x,vec <int> y,vec <int> s,vec <int> e,vec <int> l,vec <int> r){
int m = x.size();
int q = s.size();
N = n;
vec < int > g[nmax];
vec < pair < pii , pii > > quer;
for(int i = 0 ; i < q; i++){
quer.pb({{s[i],e[i]},{l[i],r[i]}});
}
for(int i = 0 ; i < m ;i++){
x[i] ++;
y[i] ++;
g[x[i]].pb(y[i]);
g[y[i]].pb(x[i]);
}
dsa.init(n);
dsb.init(n);
for(int i = 1; i <= n; i++){
for(int j : g[i]){
if(j > i)continue;
if(dsa.same(i,j))continue;
g1[i].pb(j);
pra[j][0] = i;
dsa.conn(i,j);
}
}
pra[1][0] = 0;
pra[0][0] = 0;
for(int i = n; i > 0; i--){
for(int j : g[i]){
if(j < i)continue;
if(dsb.same(i,j))continue;
g2[i].pb(j);
prb[j][0] = i;
dsb.conn(i,j);
}
}
prb[n][0] = n+1;
prb[n+1][0] = n+1;
for(int k = 1; k <= 20; k++){
for(int i = 1; i <= n+1; i++){
pra[i][k] = pra[pra[i][k-1]][k-1];
prb[i][k] = prb[prb[i][k-1]][k-1];
}
}
tour1.pb(0);
tour2.pb(0);
dfs1(1);
tim = 0;
dfs2(n);
rev.resize(n+1);
for(int i = 1; i <= n; i++){
rev[tour1[i]] = i;
}
for(int i = 1; i <= n; i++){
tour2[i] = rev[tour2[i]];
}
result.resize(q);
for(int i = 0; i < q; i++){
pair < pii , pii > qr = quer[i];
int nod = qr.fr.fr + 1;
int limit = qr.sc.sc + 1;
int l, r;
for(int k = 20 ; k >= 0 ; k--){
if(pra[nod][k] <= limit){
nod = pra[nod][k];
}
}
l = la[nod] , r = ra[nod];
int nod2 = qr.fr.sc + 1;
int limit2 = qr.sc.fr + 1;
int l1, r1;
for(int k = 20; k >= 0; k--){
if(prb[nod2][k] >= limit2){
nod2 = prb[nod2][k];
}
}
l1 = lb[nod2] , r1 = rb[nod2];
lil_qs.pb({{r1,r},{i,1}});
lil_qs.pb({{r1,l-1},{i,-1}});
lil_qs.pb({{l1-1,r},{i,-1}});
lil_qs.pb({{l1-1,l},{i,1}});
}
sort(lil_qs.begin(),lil_qs.end());
int updated = 0, processed = 0;
for(int i = 1; i <= n; i++){
while(lil_qs[processed].fr.fr <= updated){
pair < pii, pii> qq = lil_qs[processed];
result[qq.sc.fr] += qq.sc.sc * query(qq.fr.sc);
processed++;
}
update(tour2[i]);
updated++;
while(lil_qs[processed].fr.fr <= updated){
pair < pii, pii> qq = lil_qs[processed];
result[qq.sc.fr] += qq.sc.sc * query(qq.fr.sc);
processed++;
}
}
for(int i = 0 ; i < q ; i++){
result[i] = (result[i] >= 0);
}
return result;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
29096 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
29096 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
499 ms |
161844 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
29096 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
