fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i,a,b) for (auto i=(a); i<=(b); ++i)
  8. #define ffr(i,b,a) for (auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. #define pb emplace_back
  12. #define fi first
  13. #define se second
  14. #define sz(s) (int)(s).size()
  15. #define all(s) (s).begin(), (s).end()
  16. #define ms(a,x) memset(a,x,sizeof(a))
  17. #define cn continue
  18. #define re exit(0)
  19.  
  20. typedef long long ll;
  21. typedef vector<int> vi;
  22.  
  23. inline void rf(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); if(fopen(file".inp","r")){freopen(file".inp","r",stdin);freopen(file".out","w",stdout);} }
  24.  
  25. struct Node{
  26.     vector<int> Lx, Rx;
  27.     vector<int> R_sorted; // x của nửa phải
  28.     vector<ll> prefCnt;   // pref số phần tử trái có x > x_right_j
  29.     vector<int> all_sorted; // trộn cả hai nửa theo x (để lọc nhanh theo [Lx,Rx])
  30. };
  31.  
  32. struct Seg{
  33.     int n;
  34.     vector<Node> t;
  35.     vector<int> yord, xof; // yord[i]=node theo y=i, xof[i]=x
  36.     Seg(){}
  37.     Seg(const vector<int>& xof_){build(xof_);}
  38.     void build(const vector<int>& xof_){
  39.         xof=xof_; n=1; while(n<(int)xof.size()) n<<=1;
  40.         t.assign(2*n, {});
  41.         for(int i=0;i<(int)xof.size();++i){
  42.             t[n+i].all_sorted={xof[i]};
  43.         }
  44.         for(int i=n-1;i>=1;--i){
  45.             auto &L=t[i<<1].all_sorted, &R=t[i<<1|1].all_sorted;
  46.             t[i].all_sorted.resize(sz(L)+sz(R));
  47.             merge(all(L),all(R),t[i].all_sorted.begin());
  48.         }
  49.         build_pairs(1,0,n-1);
  50.     }
  51.     void build_pairs(int p,int l,int r){
  52.         if(l==r){
  53.             t[p].R_sorted = t[p].all_sorted;
  54.             t[p].prefCnt.assign(sz(t[p].R_sorted)+1,0);
  55.             return;
  56.         }
  57.         int m=(l+r)>>1;
  58.         build_pairs(p<<1,l,m);
  59.         build_pairs(p<<1|1,m+1,r);
  60.         const auto &L=t[p<<1].all_sorted;
  61.         const auto &R=t[p<<1|1].all_sorted;
  62.         t[p].R_sorted = R;
  63.         t[p].prefCnt.assign(sz(R)+1,0);
  64.         int iL=sz(L)-1;
  65.         for(int i=0;i<sz(R);++i){
  66.             while(iL>=0 && L[iL]>R[i]) --iL;
  67.             t[p].prefCnt[i+1]=t[p].prefCnt[i]+(ll)(sz(L)-(iL+1));
  68.         }
  69.     }
  70.     inline ll count_pairs_node(int p,int Lx,int Rx){ // số cặp (x_left > x_right) với x_right in [Lx,Rx], x_left free trong node
  71.         const auto &R=t[p].R_sorted;
  72.         const auto &pref=t[p].prefCnt;
  73.         auto it1=lower_bound(all(R),Lx);
  74.         auto it2=upper_bound(all(R),Rx);
  75.         int l=it1-R.begin(), r=it2-R.begin();
  76.         if(l>=r) return 0;
  77.         return pref[r]-pref[l];
  78.     }
  79.     ll query(int l,int r,int Lx,int Rx){
  80.         l+=n; r+=n;
  81.         ll res=0;
  82.         vector<int> lefts, rights;
  83.         while(l<=r){
  84.             if(l&1) lefts.pb(l++);
  85.             if(!(r&1)) rights.pb(r--);
  86.             l>>=1; r>>=1;
  87.         }
  88.         for(int id:lefts) res += count_pairs_node(id,Lx,Rx);
  89.         for(int i=sz(rights)-1;i>=0;--i) res += count_pairs_node(rights[i],Lx,Rx);
  90.         return res;
  91.     }
  92. };
  93.  
  94. int main(){
  95.     rf();
  96.     int n; if(!(cin>>n)) return 0;
  97.     vector<vi> g1(n), g2(n);
  98.     ff(i,0,n-1){
  99.         int d; cin>>d; g1[i].reserve(d);
  100.         ff(j,1,d){int x;cin>>x; g1[i].pb(x);}
  101.     }
  102.     ff(i,0,n-1){
  103.         int d; cin>>d; g2[i].reserve(d);
  104.         ff(j,1,d){int x;cin>>x; g2[i].pb(x);}
  105.     }
  106.     auto dfs=[&](const vector<vi>& g){
  107.         vi tin(n), tout(n), it(n,0); vector<char> vis(n,0);
  108.         vector<int> st; st.pb(0); int T=0;
  109.         while(!st.empty()){
  110.             int v=st.back();
  111.             if(!vis[v]){vis[v]=1; tin[v]=T++;}
  112.             if(it[v]<(int)g[v].size()){int u=g[v][it[v]++]; st.pb(u);}
  113.             else{tout[v]=T; st.pop_back();}
  114.         }
  115.         return pair<vi,vi>(tin,tout);
  116.     };
  117.     auto t1=dfs(g1), t2=dfs(g2);
  118.     vi tin1=t1.fi, tout1=t1.se, tin2=t2.fi, tout2=t2.se;
  119.  
  120.     vi ordX(n); ff(v,0,n-1) ordX[tin1[v]]=v;
  121.     vi Xpos(n); ff(i,0,n-1) Xpos[ordX[i]]=i;
  122.  
  123.     vi y2node(n); ff(v,0,n-1) y2node[tin2[v]]=v;
  124.     vector<int> XofY(n);
  125.     ff(y,0,n-1){int v=y2node[y]; XofY[y]=Xpos[v];}
  126.  
  127.     Seg seg(XofY);
  128.  
  129.     int q; cin>>q;
  130.     vector<string> ans(q);
  131.     ff(i,0,q-1){
  132.         int u,v; cin>>u>>v;
  133.         int Lx=tin1[u], Rx=tout1[u]-1;
  134.         int Ly=tin2[v], Ry=tout2[v]-1;
  135.         if(Lx>Rx || Ly>Ry){ ans[i]="YES"; cn; }
  136.         ll inv = seg.query(Ly,Ry,Lx,Rx);
  137.         ans[i]=(inv==0?"YES":"NO");
  138.     }
  139.     ff(i,0,q-1) cout<<ans[i]<<nl;
  140.     re;
  141. }
  142.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
7
3 2 3 6
0
0
2 4 1
0
0
1 5
1 5
0
0
0
3 6 1 2
2 3 4
0
4
3 5
0 4
3 3
6 5
stdout 
NO
NO
YES
YES
https://ideone.com/B23Q6I
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!