QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#135162 | #6631. Maximum Bitwise OR | SolitaryDream# | ML | 0ms | 0kb | C++20 | 2.5kb | 2023-08-05 12:17:54 | 2023-08-05 12:17:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=1e5+5;
const int M=1000000000;
const int V=60*N;
vector<int> E[V<<1];
int Tr[V<<1][2];
int K;
int New() {
++K;
Tr[K][0]=Tr[K][1]=0;
E[K<<1].clear();
E[K<<1|1].clear();
return K;
}
void Edge(int x,int y) {
E[x].push_back(y);
E[y^1].push_back(x^1);
}
#define ls Tr[p][0]
#define rs Tr[p][1]
#define lson L,mid,ls
#define rson mid+1,R,rs
void sol(int L,int R,int p,int l,int r,int id) {
if(!p) return ;
if(L==l && R==r) {
Edge(id<<1,p<<1);
return ;
}
int mid=L+R>>1;
if(r<=mid) sol(lson,l,r,id);
else if(l>mid) sol(rson,l,r,id);
else sol(lson,l,mid,id),sol(rson,mid+1,r,id);
}
void add(int L,int R,int &p,int l,int r,int id) {
int q=New();
if(p) {
Edge(q<<1,p<<1);
Tr[q][0]=Tr[p][0];
Tr[q][1]=Tr[p][1];
}
if(L==l && R==r) {
Edge(q<<1,id<<1|1);
return ;
}
int mid=L+R>>1;
if(r<=mid) add(lson,l,r,id),Edge(q<<1,Tr[q][0]<<1);
else if(l>mid) add(rson,l,r,id),Edge(q<<1,Tr[q][1]<<1);
else {
add(lson,l,mid,id);
add(rson,mid+1,r,id);
Edge(q<<1,Tr[q][0]<<1);
Edge(q<<1,Tr[q][1]<<1);
}
}
int dfn[V],low[V],stk[V],col[V];
bool mark[V];
int dfn_cnt,top,col_cnt;
void Tarjan(int x) {
dfn[x]=low[x]=++dfn_cnt;
stk[++top]=x;
mark[x]=1;
for(auto y: E[x]) {
if(!dfn[y]) Tarjan(y),low[x]=min(low[x],low[y]);
else if(mark[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]) {
col_cnt++;
while(top) {
int y=stk[top--];
mark[y]=0;
col[y]=col_cnt;
if(y==x) break;
}
}
}
void solve() {
int n,m;
cin >> n >> m;
K=0;
FOR(i,1,n) New();
int rt=0;
FOR(i,1,n) {
int l,r;
cin >> l >> r;
sol(0,M,rt,l,r,i);
add(0,M,rt,l,r,i);
}
while(m--) {
int a,b;
cin >> a >> b;
Edge(a<<1|1,b<<1);
}
dfn_cnt=col_cnt=0;
FOR(i,1,K<<1|1) dfn[i]=0;
FOR(i,1,K<<1|1) if(!dfn[i]) Tarjan(i);
int res=1;
FOR(i,1,n) if(col[i<<1]==col[i<<1|1]) res=0;
cout << (res?"YES\n":"NO\n");
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
1 3 2 10 10 5 1 2 1 3