fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifndef ONLINE_JUDGE
  5.     #include "template.cpp"
  6. #else
  7.     #define debug(...)
  8.     #define debugArr(a, n)
  9. #endif
  10.  
  11. #define io ios_base::sync_with_stdio(false); cin.tie(NULL); 
  12. #define endl '\n'
  13.  
  14. void Wah() {
  15.     io;
  16.     #ifndef ONLINE_JUDGE
  17.         freopen("input.txt", "r", stdin);
  18.         freopen("output.txt","w",stdout);
  19.     #endif
  20. }
  21.  
  22. // typedef vector<long long> vll;
  23. // typedef long double ld;
  24. // #define int long long
  25. // typedef pair<int,int> pii;
  26.  
  27.  
  28. const int N = 1e6+10;
  29. int a[N], b[N];
  30. vector<int> comp;
  31. int canJump[N];
  32. int lastSeen[N];
  33. int t[4 * 2 * N]{};
  34.  
  35. void clearAll(){ /// run for 2n
  36.  
  37. }
  38.  
  39. void compress( int n ){
  40.     comp.assign(2*n,0);
  41.     for ( int i = 1; i <= n; i++ ) comp[i-1] = a[i];
  42.     for ( int i = 1; i <= n; i++ ) comp[i-1+n] = b[i];
  43.  
  44.     sort(comp.begin(), comp.end());
  45.     comp.erase(unique(comp.begin(), comp.end()), comp.end());
  46.  
  47.     for ( int i = 1; i <= n; i++ ) {
  48.         a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin() + 1;
  49.         b[i] = lower_bound(comp.begin(), comp.end(), b[i]) - comp.begin() + 1;
  50.     }
  51. }
  52.  
  53. void calculateJump( int n ){
  54.     for ( int i = 1; i <= n; i++ ){
  55.         if ( lastSeen[a[i]] ) {
  56.             canJump[i] = i - lastSeen[a[i]] + 1;
  57.             lastSeen[b[i]] = i;
  58.         }
  59.     }
  60. }
  61.  
  62. void build(int n, int b, int e) {
  63.     if (b == e) {
  64.         t[n] = INT_MAX; ///////////
  65.         return;
  66.     }
  67.     int mid = (b + e) >> 1, l = n << 1, r = l | 1;
  68.     build(l, b, mid);
  69.     build(r, mid + 1, e);
  70.     t[n] = max(t[l], t[r]); ///////////
  71. }
  72.  
  73. void upd(int n, int b, int e, int i, int x) {
  74.     if (b > i || e < i) return;
  75.     if (b == e && b == i) {
  76.         t[n] = x; ///////////
  77.         return;
  78.     }
  79.     int mid = (b + e) >> 1, l = n << 1, r = l | 1;
  80.     upd(l, b, mid, i, x);
  81.     upd(r, mid + 1, e, i, x);
  82.     t[n] = max(t[l], t[r]); ///////////
  83. }
  84.  
  85. int query(int n, int b, int e, int i, int j) {
  86.     if (b > j || e < i) return INT_MIN; /////////////
  87.     if (b >= i && e <= j) return t[n];
  88.     int mid = (b + e) >> 1, l = n << 1, r = l | 1;
  89.     int L = query(l, b, mid, i, j);
  90.     int R = query(r, mid + 1, e, i, j);
  91.     return max(L, R); ///////////////
  92. }
  93.  
  94. void senritsu() {   
  95.  
  96.     int n; cin >> n;
  97.     for ( int i = 1; i <= n; i++ ) cin >> a[i];
  98.     for ( int i = 1; i <= n; i++ ) cin >> b[i];
  99.  
  100.     build(1,1,2*n);
  101.     compress(n);
  102.     calculateJump(n);
  103.  
  104.  
  105.  
  106. }
  107.  
  108. signed main() {
  109.     Wah();
  110.     int tt = 1;
  111.     cin >> tt;
  112.     while ( tt-- > 0 ) {
  113.         senritsu();
  114.     }
  115.     return 0;
  116. }
Success #stdin #stdout 0s 7492KB
comments (?)
stdin
copy 
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
2
5 1
1 5
5 3
1 2
2 3
3 5
stdout
copy 
Standard output is empty
https://ideone.com/vy0af8
language:
C++14 (gcc 8.3)
created:
21 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!