fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #pragma GCC optimize ("O2")
  5. #pragma GCC optimize ("unroll-loops")
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp> 
  8. #include <ext/pb_ds/tree_policy.hpp> 
  9. using namespace __gnu_pbds; 
  10. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
  11.  
  12. #define ll long long
  13. #define pii pair<ll,ll>
  14. #define fi first
  15. #define sec second
  16.  
  17. const ll MOD = 1e9 + 7;
  18. const ll N = 5e5 + 5;
  19. const ll INF = 2e18;
  20.  
  21. int32_t main(){
  22.   cin.tie(0)->sync_with_stdio(0);
  23.   int tc = 1;
  24.   cin >> tc;
  25.   while(tc--){
  26.     ll n,m,k; cin >> n >> m >> k;
  27.  
  28.     vector<ll>a(n + 5), b(m + 5);
  29.     multiset<ll>c;
  30.  
  31.     for(int i=1;i<=n;i++) cin >> a[i];
  32.     for(int i=1;i<=m;i++) cin >> b[i];
  33.     for(int i=1;i<=k;i++){
  34.       ll x; cin >> x;
  35.       c.insert(x);
  36.     }
  37.  
  38.     vector<bool>ada(n + 5);
  39.  
  40.     vector<ll>lo(n + 5, 0), hi(n + 5, n + 1);
  41.  
  42.     vector<ll>sg(4 * n + 5), lg2(n + 5);
  43.     vector<vector<ll>> mx(n + 5, vector<ll>(30));
  44.  
  45.     lg2[1] = 0;
  46.     for(int i=2;i<=n;i++){
  47.       lg2[i] = lg2[i - 1] + bool(1LL << (lg2[i - 1] + 1) == i);
  48.     }
  49.  
  50.     set<ll>id;
  51.  
  52.     function<void(ll, ll, ll, ll, ll)> upd = [&](ll l, ll r, ll cur, ll idx, ll val) -> void{
  53.       if(l == r) sg[cur] += val;
  54.       else{
  55.         ll mid = (l + r) / 2;
  56.         if(idx <= mid) upd(l, mid, cur * 2, idx, val);
  57.         else upd(mid + 1, r, cur * 2 + 1, idx, val);
  58.  
  59.         sg[cur] = sg[cur * 2] + sg[cur * 2 + 1];
  60.       }
  61.     };
  62.  
  63.     function<ll(ll, ll, ll, ll, ll)> query = [&](ll l, ll r, ll cur, ll x, ll y) -> ll{
  64.       if(l > y || r < x) return 0;
  65.       if(l >= x && r <= y) return sg[cur];
  66.  
  67.       ll mid = (l + r) / 2;
  68.       return query(l, mid, cur * 2, x, y) + query(mid + 1, r, cur * 2 + 1, x, y);
  69.     };
  70.  
  71.     ll pt = 1;
  72.     for(int i=1;i<=n;i++){
  73.       if(pt <= m && a[i] == b[pt]){
  74.         ada[b[pt]] = 1;
  75.         ++pt;
  76.       }
  77.     }
  78.  
  79.     if(pt != m + 1){
  80.       cout << "tidak\n";
  81.       continue;
  82.     }
  83.  
  84.     for(int i=1;i<=n;i++) if(ada[a[i]]) id.insert(i);
  85.  
  86.     function<void()> construct = [&]() -> void{
  87.       for(ll i=0;i<30;i++){
  88.         for(int j=1;j<=n;j++){
  89.           if(i == 0){
  90.             if(ada[a[j]]) mx[j][i] = a[j];
  91.           }
  92.           else{
  93.             if(j + (1LL << (i - 1)) <= n) mx[j][i] = max(mx[j][i - 1], mx[j + (1LL << (i - 1))][i - 1]);
  94.           }
  95.         }
  96.       }
  97.     };
  98.  
  99.  
  100.     construct();
  101.  
  102.     for(int i=1;i<=n;i++){
  103.       ll l = 1, r = i - 1;
  104.       ll ans = -1;
  105.  
  106.       while(l <= r){
  107.         ll mid = (l + r) / 2;
  108.         ll get = max(mx[mid][lg2[i - mid]], mx[i - (1LL << lg2[i - mid])][lg2[i - mid]]);
  109.  
  110.         if(get > a[i]){
  111.           ans = mid;
  112.           l = mid + 1;
  113.         }
  114.  
  115.         else r = mid - 1;
  116.       }
  117.  
  118.       if(ans != -1){
  119.         auto x = id.lower_bound(ans);
  120.         if(x != id.end() && *x == ans) lo[i] = ans;
  121.         else if(x != id.begin()) lo[i] = *(--x);
  122.       }
  123.  
  124.     }
  125.  
  126.     for(int i=n;i>=1;--i){
  127.       ll l = i + 1, r = n;
  128.       ll ans = -1;
  129.  
  130.       while(l <= r){
  131.         ll mid = (l + r) / 2;
  132.         ll get = max(mx[i][lg2[mid - i + 1]], mx[mid - (1LL << lg2[mid - i + 1]) + 1][lg2[mid - i + 1]]);
  133.         if(get > a[i]){
  134.           ans = mid;
  135.           r = mid - 1;
  136.         }
  137.  
  138.         else l = mid + 1;
  139.       }
  140.  
  141.       if(ans != -1){
  142.         auto x = id.lower_bound(ans);
  143.         if(x != id.end()) hi[i] = *x;
  144.       }
  145.  
  146.     }
  147.  
  148.     vector<ll>h;
  149.  
  150.     for(int i=1;i<=n;i++){
  151.       if(!ada[a[i]]) h.push_back(i);
  152.     }
  153.  
  154.     auto cmp = [&](ll x, ll y){
  155.       return a[x] > a[y];
  156.     };
  157.  
  158.     sort(h.begin(), h.end(), cmp);
  159.  
  160.     bool ok = 1;
  161.     for(auto i : h){
  162.       if(c.empty()){
  163.         ok = 0;
  164.         break;
  165.       }
  166.  
  167.       ll need = (hi[i] - lo[i] - 1) - query(1, n, 1, lo[i] + 1, hi[i] - 1);
  168.       auto x = c.lower_bound(need);
  169.  
  170.       if(x == c.begin() && *x > need){
  171.         ok = 0;
  172.         break;
  173.       }
  174.       if(x != c.end() && *x == need) c.erase(c.find(*x));
  175.       else c.erase(c.find(*(--x)));
  176.  
  177.       upd(1, n, 1, i, 1);
  178.     }
  179.  
  180.     ok ? cout << "ya\n" : cout << "tidak\n";
  181.   }
  182. }
  183.  
  184. /*
  185.  
  186. - akan optimal kalau kita hapus elemen yang lebih gede dulu, karena mempermudah penghapusan element" yg lbh kecil
  187. - intiny semakin gede range penghapusan semakin bgs
  188. */
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ya
https://ideone.com/fsMyhT
language:
C++14 (gcc 8.3)
created:
86 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!