QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135192#6631. Maximum Bitwise ORSolitaryDream#ML 0ms0kbC++202.7kb2023-08-05 12:40:162023-08-05 12:40:18

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:40:18]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-08-05 12:40:16]
  • 提交

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;
bool __;
const int N=1e5+5;
const int M=1000000000;
const int V=240*N;
vector<int> E[V];
int Tr[V/2][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];
        }
        p=q;
    }
    Edge((p+1)<<1,p<<1);
    if(L==l && R==r) {
        Edge(p<<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[p][0]) Edge((p+1)<<1,(Tr[p][0]+1)<<1);
    if(Tr[p][1]) Edge((p+1)<<1,(Tr[p][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;
        }
    }
}
bool ___;
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() {
    cerr << (&__-&___)/1024.0/1024 << '\n';
    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: