fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. #define           f     first
  6. #define           s     second
  7. #define           pb    push_back
  8. #define           ep    emplace
  9. #define           eb    emplace_back
  10. #define           lb    lower_bound
  11. #define           ub    upper_bound
  12. #define       all(x)    x.begin(), x.end()
  13. #define      rall(x)    x.rbegin(), x.rend()
  14. #define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
  15. #define     mem(f,x)    memset(f , x , sizeof(f))
  16. #define        sz(x)    (ll)(x).size()
  17. #define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
  18. #define          mxx    *max_element
  19. #define          mnn    *min_element
  20. #define    cntbit(x)    __builtin_popcountll(x)
  21. #define       len(x)    (int)(x.length())
  22.  
  23. const int N = 1e6 + 10;
  24. const int M = 3e5 + 10;
  25.  
  26. int A[M], B[M], mx[M], mn[M], pos[M], ans[N];
  27. vector <pair <int, int>> ask[M], add[M];
  28.  
  29. struct seg{
  30.     vector <int> seg;
  31.     void ass(int n) {
  32.         seg.assign(n * 4 + 100, 0);
  33.     }
  34.  
  35.     void upd(int id, int l, int r, int p, int v) {
  36.         seg[id] = max(seg[id], v);
  37.         if (l == r)
  38.             return;
  39.  
  40.         int m = (l + r) / 2;
  41.         if (m >= p) {
  42.             upd(id * 2, l, m, p, v);
  43.         } else {
  44.             upd(id * 2 + 1, m + 1, r, p, v);
  45.         }
  46.     }
  47.  
  48.     int get(int id, int l, int r, int u, int v) {
  49.         if (l > v || r < u)
  50.             return 0;
  51.  
  52.         if (l >= u && r <= v)
  53.             return seg[id];
  54.  
  55.         int m = (l + r) / 2;
  56.         return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
  57.     }
  58. };
  59.  
  60. int find_mex(int n, int x, int y) {
  61.     int l = 0, r = n - 1, ans = -1;
  62.     while (l <= r) {
  63.         int m = (l + r) / 2;
  64.         if (mn[m] >= x && mx[m] <= y) {
  65.             ans = m;
  66.             l = m + 1;
  67.         } else {
  68.             r = m - 1;
  69.         }
  70.     }
  71.  
  72.     return ans + 1;
  73. }
  74.  
  75. void cal(int n) {
  76.     seg seg;
  77.     seg.ass(n);
  78.     for (int i = 1; i <= n; i++) {
  79.         mx[B[i]] = mn[B[i]] = i;
  80.         pos[A[i]] = i;
  81.     }
  82.  
  83.     for (int i = 1; i < n; i++) {
  84.         mx[i] = max(mx[i - 1], mx[i]);
  85.         mn[i] = min(mn[i - 1], mn[i]);
  86.     }
  87.  
  88.     int l = n, r = 1;
  89.     for (int i = 0; i < n; i++) {
  90.         l = min(l, pos[i]);
  91.         r = max(r, pos[i]);
  92.         add[r].pb({l, i + 1 - find_mex(n, l, r)});
  93.     }
  94.  
  95.     for (int i = 1; i <= n; i++) {
  96.         for (auto x : add[i]) {
  97.             seg.upd(1, 1, n, x.f, x.s);
  98.         }
  99.  
  100.         for (auto x : ask[i]) {
  101.             ans[x.s] = max(seg.get(1, 1, n, x.f, i), ans[x.s]);
  102.         }
  103.  
  104.         add[i].clear();
  105.     }
  106. }
  107.  
  108. void solve() {
  109.     int n;
  110.     cin >> n;
  111.  
  112.     for (int i = 1; i <= n; i++)
  113.         cin >> A[i];
  114.  
  115.     for (int i = 1; i <= n; i++)
  116.         cin >> B[i];
  117.  
  118.     int q;
  119.     cin >> q;
  120.  
  121.     for (int i = 1; i <= q; i++) {
  122.         int l, r;
  123.         cin >> l >> r;
  124.         ask[r].pb({l, i});
  125.     }
  126.  
  127.     cal(n);
  128.     for (int i = 1; i <= n; i++) {
  129.         swap(A[i], B[i]);
  130.     }
  131.  
  132.     cal(n);
  133.     for (int i = 1; i <= n; i++)
  134.         ask[i].clear();
  135.  
  136.     for (int i = 1; i <= q; i++) {
  137.         cout << ans[i] << "\n";
  138.         ans[i] = 0;
  139.     }
  140. }
  141.  
  142. int main() {
  143.     ios_base::sync_with_stdio(0);
  144.     cin.tie(0);
  145.     cout.tie(0);
  146.  
  147.     int t;
  148.     cin >> t;
  149.  
  150.     while (t--) {
  151.         solve();
  152.     }
  153.  
  154.     return 0;
  155. }
  156.  
  157. // ab a
Time limit exceeded #stdin #stdout 5s 18772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rm1Tf9
language:
C++14 (gcc 8.3)
created:
134 days ago
visibility:
secret

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!