#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC target("popcnt")
#define endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
#define pq_min(a) priority_queue<a, vector<a>, greater<a>>
#define fls cout.flush()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using ii = pair<int,int>;
using mii = map<int,int>;
using lld = long double;
void valid(ll in){cout<<((in)?"YES\n":"NO\n");}
ll lcm(ll a, ll b){return (a/gcd(a,b))*b;}
const int LOG = 20;
int query(int l, int r, vector<vi>&sp){
int lg = log2(r-l+1);
return min(sp[l][lg], sp[r-(1<<lg)+1][lg]);
}
vi check_validity(int N, vi X, vi Y,vi S, vi E,vi L, vi R) {
int Q = S.size(), M = sz(X);
vi ans(Q,0), cn(N), P(N), A(N);
vector<vi> graph(N);
fo(i,M)cn[X[i]]++,cn[Y[i]]++,graph[X[i]].pb(Y[i]),graph[Y[i]].pb(X[i]);
fo(i,N){
if(cn[i]==1){
P[i] = 0;
int j = graph[i][0], p = i;
int c=1;
while(cn[j]==2){
P[j]=c++;
if(graph[j][0]==p)p=j,j=graph[j][1];
else p=j,j=graph[j][0];
}
P[j]=c;
break;
}
}
fo(i,N)A[P[i]] = i;
vector<vi> sp(N, vi(LOG, 0));
fo(i,N)sp[i][0]=A[i];
for(int bit = 1; bit < LOG; bit++){
for(int i = 0;i<N-(1<<bit)+1; i++){
sp[i][bit] = max(sp[i][bit-1] , sp[i+(1<<(bit-1))][bit-1]);
}
}
vector<vector<array<int,4>>> queries(N);
for (int i = 0; i < Q; ++i) {
if(P[S[i]] > P[E[i]])swap(S[i], E[i]);
queries[L[i]].pb({R[i], S[i], E[i], i});
}
set<int> menores;
fo(i,N)menores.insert(P[i]);
menores.insert(N);
ffo(i,N){
menores.erase(P[i]);
for(auto qq : queries[i]){
int next_menor=(*menores.lower_bound(P[qq[1]]));
next_menor--;
if(next_menor<P[qq[1]])continue;
int l=P[qq[1]],r=P[qq[2]];
while(l<=r){
int m=(l+r)/2;
if(query(m, P[qq[2]], sp) <= qq[0])r=m-1;
else l=m+1;
}
if(l<=next_menor)ans[qq[3]] = 1;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
494 ms |
75024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
