QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135178#6631. Maximum Bitwise ORSolitaryDream#ML 0ms0kbC++202.6kb2023-08-05 12:29:042023-08-05 12:29:06

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 12:29:06]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-08-05 12:29:04]
  • 提交

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)<<1);
        return ;
    }
    Edge(id<<1,p<<1);
    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();
    New();
    if(p) {
        Edge(q<<1,p<<1);
        Tr[q][0]=Tr[p][0];
        Tr[q][1]=Tr[p][1];
    }
    Edge((q+1)<<1,q<<1);
    if(L==l && R==r) {
        Edge(q<<1,id<<1|1);
    } else {
        int mid=L+R>>1;
        if(r<=mid) add(lson,l,r,id);
        else if(l>mid) add(rson,l,r,id);
        else {
            add(lson,l,mid,id);
            add(rson,mid+1,r,id);
        }
    }
    if(Tr[q][0]) Edge((q+1)<<1,(Tr[q][0]+1)<<1);
    if(Tr[q][1]) Edge((q+1)<<1,(Tr[q][1]+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;
}

詳細信息

Test #1:

score: 0
Memory Limit Exceeded

input:

1
3 2
10 10 5
1 2
1 3

output:


result: