fork download
copy 
  1. // █▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█
  2. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  3. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  4. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄▄█▀███▀▀▀▀▀██▀▀▀▀▄▄▄▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  5. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄█▀▀░░▄▄██▀▀░░░▄█▀░░░░░░░▄█▀█▄▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  6. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄█▀▀░░░▄▄█▀█▀░░░░▄█░░░░░░░░░░░▀█░▀███▄▄░░░░░░░░░░░░░░░░░░░░░░░░░░█
  7. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄█▀░▄▄░▄█▀░░▄▀░░░░▄█░░░░░░░░░░░░░▀█░░█▄░▀█▄░░░░░░░░░░░░░░░░░░░░░░░░█
  8. // █░░░░░░░░░░░░░▄▄▄▄▄▄▄░░░░░░░░░░█▀▄█▀▀░█▀░░▄█▀░░░░█▀░░░░░░░░░░░░░░░█░░░█░░░░▀█░░░░░░░░░░░░░░░░░░░░░░█
  9. // █░░░░░░░░░░░░▀█▄▄▄▄▄█▀█▄░░░░░▄▀▄█▀░░░█░░░▄█░░░░░░█░░░░░░░░░░░░░░░░█░░░█░░░░░░█▄░░░░░░░░░░░░░░░░░░░░█
  10. // █░░░░░░░░░░░▄▄▀▀░░░░▀▀░▀█░░▄███▀░░░░░█░░░█░░░░░░░█░░░░░░░░▄░░░░░░░█░░░█░░░░░█░▀█▄░░░░░░░░░░░░░░░░░░█
  11. // █░░░░░░░░░▄█▀▄█▀░░▄█░░░░▀█▄▀▄█░░▄░░░░▀░░░░░░░░░░▄█░░░░░░░░█░░░░░░░█░░░█░░░░░█░░░█▄░░░░░░░░░░░░░░░░░█
  12. // █░░░░░░░░██▄██▀░░█▀░░▄▄▄▀▄██▀░░░█░░▄░░░░░░░░░░░░█▀░░░░░░░█▀░░░░░░██░░░█░░░░░█░░░░█▀▄░░░░░░░░░░░░░░░█
  13. // █░░░░░░░░▀░░█▀░▄██▄▄█▀░░▄██░░░░░█░░█░░░░░▄░░░░░░▀█░░░░░░░█░░░░░░▄█░░░░█░░░░░█░░░░░░▀█▄░░░░░░░░░░░░░█
  14. // █░░░░░░░░░░░█▄█▀░█▀░░░░▄█▀░░░░░░█░░█░░░░░█░░░░░░░█░░░░░░░█░░░░░▄█░░░░▄█░░░░░█░░░░░░░░▀▄▄▄█▀▀█▄░░░░░█
  15. // █░░░░░░░░░░░▀▄▄██▀▄▄▄▀▀▀█░░░░░░░█░░█░░░░░█░▄▄▄▄▄▄▀▀▀▀▀▀▀▀█▄▄▄▄▄█▄▄░░░█░░░░░░█░░░▄░░░░░█░░▄▄▄░█░░░░░█
  16. // █░░░░░░░░░░▄█▀▄█░▀█░░░░█▀░░░░░░░█░░█░█░░░███▄█▀██████▀▀▀▀▀░░░░░░░▀▀█▄█░░░░░▄█░░░█░░░░░█░░░▀████░░░░█
  17. // █░░░░░░░░░█▀░█▀░░░█░░░░█░░░░░░░░█░░█░█▄░█▀░░░░░▀███▄▀▀░░░░░░░░░▀▀▀█▄██▄▄▄░░█░░░░█░░░░░█░░░░░▀▀█▄░░░█
  18. // █░░░░░░░░▄█▄░░░▄▄█░░░░░█░░░░░░░░█░░█▀▀▀▀░░░░░░░██▄██░░░░░░░░░░░░█▀███▀▀▄█▀▀▀█▄▄░█░░░░░▀█░░██▄░░█▄░░█
  19. // █░░░░░░░█▀▄██▀██░░░░░░░█░░░░░░░░█▄░▀█░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄███░░░▀█▄░░░▀▀█░░░█░░█░░▀█▀▀█▄█░░█
  20. // █░░░░░░░█░▀░░▄█░░░░░░░░█░░░░░░░░░█▄░▀█▄░░░▄▄▄▄▄▄▄▄▄▄░░░░░█▀░░░░░▀▀▀▀░░░░░░▀█░░░▄█░░▄▀░░█░▄▄█░░░▀▀░░█
  21. // █░░░░░░▄▀░░▄█▀░░░░░░░█▀█░░░░░▄░░░░█▄░░▀█▀▀▀░░░░░░░░░░░░░░░░░░░░▀█▄▄▄░░░░░░░░█▄░█░░▄█░░░██▀░░░░░░░░░█
  22. // █░░░░░██░▄█▀█░░░░░░░░█░▀▄░░░░░█░░░▀██▄▄▀█▄░░░░░░░░░░░░░▀▀░░░░░░░░░░▀▀█▄▄░░░░░██▀░▄█░░░███░░░░░░░░░░█
  23. // █░░░░▄█▀█▀░▄▀░░░░░░░░█░░█░░░░░░█▄░░▀▄░░▀▀██░░░░░░░▄▄▄▄▄▄▄▄▄░░░░░░░░░░░░▀▀▄▄▄▄█▄▄▀▀░░░░█░▀▄░░░░░░░░░█
  24. // █░░░░█░░░▄█▀░░░░░░░░░█▄░█▄░░░░░░▀█▄░▀█░░░░░▄▀▀▄░█▀▀░░░░░░░▀▀▀▀█▄░░░░░░░░░░░░█▀█░░░░░░░█░░█░░░░░░░░░█
  25. // █░░░░▀█░▄▀█░░░░░░░░░░░▀█▄██░░░░░░░░████▄░░█▀░░░▀░░░░░░░░░░░░░░░▀▀▄░░░░░░░░░░░░█░░░░░░█▀░░█▄░░░░░░░░█
  26. // █░░░░░█▄▀░█░░░░░░░░░░░░█░░░░░░█▀█▄░█▄░░▀▀░█░░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░░░░██▀█░░░▀▄░░░█░░░░░░░░█
  27. // █░░░░█▀░░░█▄▄░░░░░░░░░░█░░░██▄█░░▀█▄▀▄░░░░█▄░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░▄▄▀░▄█▀▀▀█░▀█▄░█░░░░░░░░█
  28. // █░░░░▀▄▄▄▄█▄▀█░░░░░░▄▄▄██▄▄█▄██▄░░██▄██░░░░█░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░█░░▄▀░░█▀█░░░░░█░░░░░░░░█
  29. // █░░░░░▀█▀░░░▄█▄█▀▀▀▀▀░░░░░░░█░██░░█░█▄▄▀▀▀▀▀▀▀▀▄▄▄▄▄▄░░░░░░░░░░░█▀░░░██▄░░█▀▄█░░▄█░░█░░░▄▄█░░░░░░░░█
  30. // █░░░░░░█▄░▄█▀░░░░░░░░░░░░░░░░█░█▄░█░█░▀█░░░░░░░░░░░░█▀▀▀▀▀▀▄▄▄▄██░░░█▀░█░█▀█▀░▄▄▀░▄█▀░░▀▀░█░░░░░░░░█
  31. // █░░░░░░░█▀▀░░░░░░░░░░░░░░░░░░█▄░█░█░█░░█░░░░░░░░░░░░█░░░░▄▄▄░░█░▀▀▀▀█░░██▀░░▄█▀░▄█▀░▀█░░░░█░░░░░░░░█
  32. // █░░░░░░█░░░░░░▄▄████████▄░░░░░█░░░█▄█░░█░░░░░░░░░░░░█░░░░███░░█░░░░░█░▄█▀░░░░░▄██▄░░░▀▀░░█░░░░░░░░░█
  33. // █░░░░░░█░░░░░█████████████▄░░░▀█░░░░▀░░▀▄░░░░░░░░░░░█░░░░░░░░░█░░░░░█▄▀░░░░▄░░█░░░▀█▄▄█▀▀░░░░░░░░░░█
  34. // █░░░░░░█▄░░░░▀███████▀▀▀▀▀█▄░░░▀▄░░░░░░░█░░░░░░░░░░░█░░░░░░░░░█░░░░█▀▀░░▄█▀░░█░░░░░██░░░░░░░░░░░░░░█
  35. // █░░░░░░░█░░░░░░███▀░░░░░░░░▀▄░░░▀█░░░░░░█░░░░░░░░░░░█░░░░░░░░░█░░░█▀░░░█▀░░░█▀░░░░▄█░░░░░░░░░░░░░░░█
  36. // █░░░░░░░▀▄░░░░░██░░░░░░░░░░░░▀░░░█░░░░░░▀█░░▄▄░░░░░░█░░░░░░░░▄█░░░█░░▄█░░░░░█░░░░░█░░░░░░░░░░░░░░░░█
  37. // █░░░░░░░░▀█░░▄█▀░░░░░░░░░░░░░░░░▄█░░░░░░░▀█░▀▀▀▀▀█▄▄█▄▄▄▄▄▄▄▄█▄▄▄█▀░░█░░░░░▄█░░░░░█░░░░░░░░░░░░░░░░█
  38. // █░░░░░░░░░█░▄▀░░░░░░░░░░░░░░░▄█▀▀▀█▄░░░░░░▀█░░░░░░▀▀██████████████░░█▀░░░░░█░░░░░█▀░░░░░░░░░░░░░░░░█
  39. // █░░░░░░░░░██▀░░░░░░░░░░░░░░▄██░░░░░█▄░░░░░░█░░░░░░░░█░░░░░▀▀▀▀▀█▀█░░█░░░░░░█░░░░░█░░░░░░░░░░░░░░░░░█
  40. // █░░░░░░░░░██▀░░░░░░░░░░░░░░██░░░░░░░█▄░░░░░█░░░░░░░░█░░░░░░░░░░█░▀█▄█░░░░░░███▄░░▀▄░░░░░░░░░░░░░░░░█
  41. // █░░░░░░░░░██▄▄░░░░░░░░░░░░▄██░░░░░░░░▀█▄░▄█▀░░░░░░░░█░░░░░░░░░▄█░░█▄░░░░░░░██░▀█▄░▀█░░░░░░░░░░░░░░░█
  42. // █░░░░░░░▄██▀░▀█▄░░░░░░░░░░██▀░░░░░░░░░░▀▀█░░░░░░░░░▄▀░░░░░░░░▄█░░░██▄░░░░░▄██░░░█▄░▀█░░░░░░░░░░░░░░█
  43. // █░░░░░░░██▀░░░░▀▀▄▄░░░░░░██▀█▄░░░░░░░░░░░▀▀▄▄▄▄▄▄▄▄█▄▄▄▄▄▄▄░░█░░░▄▀░█░░░░░▀░█░░░░▀▄░▀█░░░░░░░░░░░░░█
  44. // █░░░░░░██▀░░░░░░░░▀█▄░░▄██▀░░░▀▄░░░░░░░░░░░░▀██████████████████▄█▀░░▀█░░░░░░█░░░░░█▄░▀▄░░░░░░░░░░░░█
  45. // █░░░░░░██░░░░░░░░░░░▀█▄██▀░░░░░░█▄░░░░░░░░░░░▀███████████████████░░░░▀█░░░░█▀░░░░░░█░░█░░░░░░░░░░░░█
  46. // █░░░░░██░░░░░░░░░░░░░░██▀░░░░░░░░▀█▄░░░░░░░░░░▀█████████████████▀░░░░░▀█░░▄█░░░░░░░█▄░░█░░░░░░░░░░░█
  47. // █░░░░▄█░░░░░░░░░░░░░▄██▀░░░░░░░░░░░▀█▄░░░░░░░░░▀████████████████░░░░░░░▀▄█▀░░░░░░░█▀█░░▀▄░░░░░░░░░░█
  48. // █░░░░█░░░░░░░░░░░░▄▄██▀░░░░░░░░░░░░░░█▄░░░░░░░░░░██▀▀▀▀▀▀██▀▀▀█▀░░░░░░░░█▀░░░░░░░▄█░█▄░░▀█▄░░░░░░░░█
  49. // █░░░░█░░░░░░░░░░░███▀░░░░░░░░░░░░░░░░░█▄░░░░░░░░░░█▄░░░░░█░░░░█░░░░░░░▄█▀░░░░░░░▄█░░░█░░░░▀▄░░░░░░░█
  50. // █▄▄▄▄█▄▄▄▄▄▄▄▄▄▄██▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄█▄▄▄▄▄█▄▄▄▄█▄▄▄▄▄▄▄█▄▄▄▄▄▄▄▄▄█▄▄▄▄█▄▄▄▄▄██▄▄▄▄▄▄█
  51. #include<bits/stdc++.h> 
  52. using namespace std;
  53. int t,n,m,k;
  54. int p[300002];
  55. int a[300002];
  56. pair<int,int>b[300002];
  57. int nxr[300002],nxl[300002];
  58. int rmb[300002][19];
  59. int dp[300002];
  60. int trc[300002];
  61. int getrmb(int i,int j){
  62.     int lij=log2(j-i+1);
  63.     return max(rmb[i][lij],rmb[j-(1<<lij)+1][lij]);
  64. }
  65. pair<pair<int,int>,int>bth[300002];
  66. pair<pair<int,int>,int>db[300002];
  67. pair<pair<int,int>,int>ds[900002];
  68. int bthsiz,dbsiz;
  69. int ans;
  70. vector<int>ansl;
  71. vector<int>lside[22],rside[22];
  72. int lsiz,rsiz;
  73. void build(int l,int r,bool side,int h){
  74.     if(h>=22)return;
  75.     for(int i=l;i<=r;i++){
  76.         if(side)rside[h].push_back(i);
  77.         else lside[h].push_back(i);
  78.     }
  79.     if(l==r)return;
  80.     int mid=(l+r)/2;
  81.     build(l,mid,0,h+1);
  82.     build(mid+1,r,1,h+1);
  83. }
  84. bool cmp(pair<pair<int,int>,int>x,pair<pair<int,int>,int>y){
  85.     return x.first.second<y.first.second;
  86. }
  87. void solve(){
  88.     for(int i=1;i<=n;i++)dp[i]=100000000;
  89.     dp[0]=0;
  90.     for(int i=1;i<=lsiz;i++){
  91.         int u=ds[i].first.first,v=ds[i].first.second;
  92.         if(dp[u-1]+1<dp[v]){
  93.             dp[v]=dp[u-1]+1;
  94.             trc[v]=i;
  95.         }
  96.     }
  97.     for(int i=1+300000;i<=bthsiz+300000;i++){
  98.         int u=ds[i].first.first,v=ds[i].first.second;
  99.         if(dp[u-1]+1<dp[v]){
  100.             dp[v]=dp[u-1]+1;
  101.             trc[v]=i;
  102.         }
  103.     }
  104.     for(int i=1+600000;i<=rsiz+600000;i++){
  105.         int u=ds[i].first.first,v=ds[i].first.second;
  106.         if(dp[u-1]+1<dp[v]){
  107.             dp[v]=dp[u-1]+1;
  108.             trc[v]=i;
  109.         }
  110.     }
  111.  
  112.     if(dp[n]==100000000)return;
  113.     if(dp[n]<ans||ans==-1){
  114.         ans=dp[n];
  115.         ansl.clear();
  116.         int i=n;
  117.         while(i>0){
  118.             ansl.push_back(ds[trc[i]].second);
  119.             i=ds[trc[i]].first.first-1;
  120.         }
  121.     }
  122. }
  123. void process(){
  124.     for(int i=1;i<=k;i++){
  125.         if(b[i].second-b[i].first+1<n)continue;
  126.         if(getrmb(b[i].first,b[i].second-n+1)==n){
  127.             cout<<"1\n"<<i<<"\n";
  128.             return;
  129.         }
  130.     }
  131.     bthsiz=0;;dbsiz=0;
  132.     ansl.clear();
  133.     ans=-1;
  134.     for(int i=0;i<22;i++){
  135.         lside[i].clear();
  136.         rside[i].clear();
  137.     }
  138.     for(int i=1;i<=k;i++){
  139.         if(nxr[b[i].first]>=b[i].second){
  140.             bth[++bthsiz]=(make_pair(make_pair(a[b[i].first],a[b[i].second]),i));
  141.         }
  142.         else if(a[nxr[b[i].first]]==n&&a[nxl[b[i].second]]==1){
  143.             db[++dbsiz]=(make_pair(make_pair(a[b[i].second],a[b[i].first]),i));
  144.         }
  145.         else if(a[nxr[b[i].first]]==n){
  146.             bth[++bthsiz]=(make_pair(make_pair(a[b[i].first],n),i));
  147.         }
  148.         else if(a[nxl[b[i].second]]==1){
  149.             bth[++bthsiz]=(make_pair(make_pair(1,a[b[i].second]),i));
  150.         }
  151.     }
  152.     if(bthsiz)sort(bth+1,bth+bthsiz+1,cmp);
  153.     for(int i=1;i<=bthsiz;i++)ds[300000+i]=bth[i];
  154.     if(!dbsiz){
  155.         lsiz=0;rsiz=0;
  156.         solve();
  157.         cout<<ans<<"\n";
  158.         if(ans!=-1){
  159.             for(int i=ansl.size()-1;i>=0;i--)cout<<ansl[i]<<" ";
  160.             cout<<"\n";
  161.         }
  162.         return;
  163.     }   
  164.     build(1,dbsiz,0,0);
  165.     for(int i=0;i<22;i++){
  166.         if(lside[i].empty()&&rside[i].empty())break;
  167.         lsiz=0;rsiz=0;
  168.         for(int j:lside[i])ds[++lsiz]=(make_pair(make_pair(1,db[j].first.first),db[j].second));
  169.         for(int j:rside[i])ds[++rsiz+600000]=(make_pair(make_pair(db[j].first.second,n),db[j].second));
  170.         solve();
  171.         lsiz=0;rsiz=0;
  172.         for(int j:rside[i])ds[++lsiz]=(make_pair(make_pair(1,db[j].first.first),db[j].second));
  173.         for(int j:lside[i])ds[++rsiz+600000]=(make_pair(make_pair(db[j].first.second,n),db[j].second));
  174.         solve();
  175.     }
  176.     cout<<ans<<"\n";
  177.     if(ans!=-1){
  178.         for(int i=ansl.size()-1;i>=0;i--)cout<<ansl[i]<<" ";
  179.         cout<<"\n";
  180.     }
  181. }
  182. void init(){
  183.     cin>>t;
  184.     while(t--){
  185.         cin>>n>>m>>k;
  186.         for(int u,i=1;i<=n;i++){
  187.             cin>>u;
  188.             p[u]=i;
  189.         }
  190.         a[0]=-1;
  191.         for(int i=1;i<=m;i++){
  192.             cin>>a[i];
  193.             a[i]=p[a[i]];
  194.             if(a[i]==a[i-1]+1)nxl[i]=nxl[i-1];
  195.             else nxl[i]=i;
  196.         }
  197.         a[m+1]=-1;
  198.         for(int i=m;i;i--){
  199.             if(a[i]==a[i+1]-1)nxr[i]=nxr[i+1];
  200.             else nxr[i]=i;
  201.             rmb[i][0]=nxr[i]-i+1;
  202.         }
  203.         for(int j=1;j<19;j++){
  204.             for(int i=1;i+(1<<j)-1<=m;i++)rmb[i][j]=max(rmb[i][j-1],rmb[i+(1<<(j-1))][j-1]);
  205.         }
  206.         for(int i=1;i<=k;i++)cin>>b[i].first>>b[i].second;
  207.         process();
  208.     }
  209. }   
  210. int main(){
  211.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  212.     init();
  213. }
  214.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SIBFLS
language:
C++ (gcc 8.3)
created:
20 hours 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!