//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "werewolf.h"
const int maxn = 4e5+10;
int n;
int st[maxn][20];
vector <pii> edge;
int f[maxn],idx[maxn],node[maxn],lc[maxn],rc[maxn];
int dfn = 0;
pii rg[maxn],qs[maxn];
int w[maxn];
int tree[maxn];
void update(int x) {
x++;
while (x<maxn) {
tree[x]++;
x += lowbit(x);
}
return;
}
int query(int x) {
x++;
int ret = 0;
while (x>0) {
ret += tree[x];
x-=lowbit(x);
}
return ret;
}
struct QQ{
int val;
int ss;
pii range;
int id;
} q[maxn];
bool cmpq(QQ x,QQ y) {
return x.ss<y.ss;
}
int ans[maxn];
bool cmp1(pii x,pii y) {
return min(x.fi,x.se) > min(y.fi,y.se);
}
bool cmp2(pii x,pii y) {
return max(x.fi,x.se) < max(y.fi,y.se);
}
int getf(int x) {
if (f[x]==x) return x;
return f[x] = getf(f[x]);
}
void dfs(int u) {
if (u<n) idx[u] = rg[u].fi = rg[u].se = dfn++;
else {
dfs(lc[u]),dfs(rc[u]);
rg[u] = {rg[lc[u]].fi,rg[rc[u]].se};
assert(rg[lc[u]].se+1==rg[rc[u]].fi);
}
rep(i,1,20) {
if (st[u][i-1]==-1) break;
st[u][i] = st[st[u][i-1]][i-1];
}
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
int tot = N;
memset(st,-1,sizeof(st));
n = N;
rep(i,0,SZ(X)) edge.pb({X[i],Y[i]});
sort(ALL(edge),cmp1);
rep(i,0,N) f[i] = i;
for (auto it:edge) {
int fx = getf(it.fi),fy = getf(it.se);
if (fx==fy) continue;
st[fx][0] = st[fy][0] = tot;
f[tot] = tot;
w[tot] = min(it.fi,it.se);
lc[tot] = fx, rc[tot] = fy;
f[fx] = f[fy] = tot++;
}
dfs(tot-1);
rep(i,0,SZ(S)) {
int u = S[i];
for (int j = 19;j>=0;j--)
if (st[u][j]!=-1 and w[st[u][j]]>=L[i]) u = st[u][j];
qs[i] = rg[u];
}
rep(i,0,n) node[idx[i]] = i;
//------
tot = n;
memset(st,-1,sizeof(st));
sort(ALL(edge),cmp2);
rep(i,0,N) f[i] = i;
for (auto it:edge) {
int fx = getf(it.fi),fy = getf(it.se);
if (fx==fy) continue;
st[fx][0] = st[fy][0] = tot;
f[tot] = tot;
w[tot] = max(it.fi,it.se);
lc[tot] = fx, rc[tot] = fy;
f[fx] = f[fy] = tot++;
}
dfs(tot-1);
rep(i,0,SZ(S)) {
int u = E[i];
for (int j=19;j>=0;j--)
if (st[u][j]!=-1 and w[st[u][j]]<=R[i]) u = st[u][j];
q[i*2].id = q[i*2+1].id = i;
q[i*2].range = q[i*2+1].range = rg[u];
q[i*2].ss = qs[i].fi-1, q[i*2+1].ss = qs[i].se;
q[i*2].val = -1, q[i*2+1].val = 1;
}
sort(q,q+SZ(S)*2,cmpq);
int cur = 0;
for (auto it:q) {
if (it.ss<0) continue;
while (cur<=it.ss) update(idx[node[cur++]]);
ans[it.id] += it.val * (query(it.range.se) - query(it.range.fi-1));
}
vector <int> ret;
rep(i,0,SZ(S)) {
assert(ans[i]>=0);
ret.pb((ans[i]>0));
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
39508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
39508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
503 ms |
65076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
39508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
