QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#734573#6633. Exam RequirementsVedant18WA 168ms76428kbC++234.5kb2024-11-11 12:51:582024-11-11 12:51:59

Judging History

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

  • [2024-11-11 12:51:59]
  • 评测
  • 测评结果:WA
  • 用时:168ms
  • 内存:76428kb
  • [2024-11-11 12:51:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define in(a, b) for (ll i = (a); i <= (b); i++)                // in using i
#define inj(a, b) for (ll j = (a); j <= (b); j++)               // in using j
#define ink(a, b) for (ll k = (a); k <= (b); k++)               // in using k
#define inl(a, b) for (ll l = (a); l <= (b); l++)               // in using l
#define inr(a, b) for(ll i = (a); i >= (b); i--)                // in reverse
#define inrj(a, b) for(ll j = (a); j >= (b); j--)                // in reverse
#define inrk(a, b) for(ll k = (a); k >= (b); k--)                // in reverse
#define inrl(a, b) for(ll l = (a); l >= (b); l--)                // in reverse
#define tt ll tcs; cin>>tcs; while(tcs--)                       // include test cases
#define ina(arr,n) ll arr[(n+1)]={0}; in(1,n) cin>>arr[i]       // input arr of n elements
#define inv(vec,n) vector<ll> vec(n+1); vec[0]=0; in(1,n) cin>>vec[i]; // input vector of n elements
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pll pair <ll,ll>
#define vpll vector <pll>
#define sll set <ll>
#define vll vector<ll>
#define mll map <ll,ll>
#define all(x) x.begin(), x.end()
const ll mod=1e9+7;
#define vvll vector<vll>
#define pref(p,a,n) vll p(n+1); in(1,n) p[i]=p[i-1]+a[i];
#define vec2(a,n,m) vvll a(n+1,vll(m+1))
// #define vec2(a,n,m,val) vvll a(n+1,vll(m+1,val))

#define vec3(a,l,m,n) vector<vvll>a(l+1,vvll(m+1,vll(n+1)));
// #define vec3(a,l,m,n,val) vector<vvll>a(l+1,vvll(m+1,vll(n+1,val)));
# define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main(){
    FAST
    tt{
        ll n,m;cin>>n>>m;
        vpll inp(n+1);
        in(1,n){
            cin>>inp[i].first>>inp[i].second;
        }
        sort(all(inp));
        ll N=(1<<ll(ceil(log2(n))));
        vvll adj(4*N);
        for(int v=1;v<N;v++){
            adj[v].push_back(2*v);
            adj[v].push_back(2*v+1);
            adj[2*N+(2*v)].push_back(2*N+v);
            adj[2*N+2*v+1].push_back(2*N+v);
        }
        vll vec;
        function<void(int,int,int,int,int) >find=[&](ll v, ll tl, ll tr,ll l, ll r){
            if(l>r){
                return ;
            }
            if(tl==l&&r==tr){
                vec.push_back(v);
                return;
            }
            ll tm=(tl+tr)/2;
            find(2*v,tl,tm,l,min(r,tm));
            find(2*v+1,tm+1,tr,max(l,tm+1),r);
        };
        in(1,n){
            ll lo=i;
            ll hi=n;
            ll ans=i;
            while(lo<=hi){
                ll mid=(lo+hi)/2;
                if(inp[mid].first<=inp[i].second){
                    ans=mid;
                    lo=mid+1;
                }
                else{
                    hi=mid-1;
                }
            }
            //i+1...ans
            find(1,1,N,i+1,ans);
            for(auto x:vec){
                // adj[2*N+i-1].push_back(x);
                adj[3*N+i-1].push_back(x);
                adj[2*N+x].push_back(N+i-1);
            }
            vec.clear();
        }
        in(1,m){
            ll a,b;
            cin>>a>>b;
            // adj[2*N+a-1].push_back(N+b-1);
            // adj[2*N+b-1].push_back(N+a-1);
            adj[N+a-1].push_back(3*N+b-1);
            adj[N+b-1].push_back(3*N+a-1);

        }
        ll NN=4*N;
        vvll r_adj(NN);
        in(1,NN-1){
            for(auto x:adj[i]){
                r_adj[x].push_back(i);
            }
        }
        vll vis(NN);
        vll ord;
        function<void(int)>dfs=[&](int v){
            vis[v]=1;
            for(auto x:adj[v]){
                if(vis[x]==0){
                    dfs(x);
                }
            }
            ord.push_back(v);
        };
        in(1,NN-1){
            if(vis[i]==0){
                dfs(i);
            }
        }
        reverse(all(ord));
        // vis.assign(0,NN+1);
        vis.clear();
        vis.resize(NN);
        ll id=1;
        function<void(int)>dfs2=[&](int v){
            vis[v]=id;
            for(auto x:r_adj[v]){
                if(vis[x]==0){
                    dfs2(x);
                }
            }
        };
        for(auto x:ord){
            if(vis[x]==0){
                dfs2(x);
                id++;
            }
        }
        bool ok=1;
        in(1,n){
            if(vis[3*N+i-1]==vis[N+i-1]){
                ok=0;
            }
        }
        cout<<(ok?"YES\n":"NO\n");
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3896kb

input:

2
3 1
1 5
2 7
10 11
2 1
3 3
1 5
2 7
5 7
1 2
2 3
3 1

output:

YES
NO

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 168ms
memory: 76428kb

input:

1
100000 100000
15084647 15220430
217541056 217598054
222963701 223110976
71224450 71340221
320463268 320631387
334861459 334924668
328950591 329083669
178996498 178996584
428529461 428605033
405428435 405504132
197936687 197947412
9058562 9190197
169407597 169474101
297518153 297590927
31471874 316...

output:

YES

result:

wrong answer 1st lines differ - expected: 'NO', found: 'YES'