fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Modulus as given:
  5. static const int MOD = 998244353;
  6.  
  7. int main(){
  8.     ios::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.  
  11.     int t;
  12.     cin >> t;
  13.     while(t--){
  14.         int n;
  15.         cin >> n;
  16.  
  17.         vector<int> p(n), q(n);
  18.         for(int i = 0; i < n; i++){
  19.             cin >> p[i];
  20.         }
  21.         for(int i = 0; i < n; i++){
  22.             cin >> q[i];
  23.         }
  24.  
  25.         // 1) Build inverse‐permutations posP, posQ in O(n)
  26.         vector<int> posP(n), posQ(n);
  27.         for(int i = 0; i < n; i++){
  28.             posP[ p[i] ] = i;
  29.             posQ[ q[i] ] = i;
  30.         }
  31.  
  32.         // 2) Build prefix‐max arrays P[i] = max(p[0..i]), Q[i] = max(q[0..i]) in O(n)
  33.         vector<int> P(n), Q(n);
  34.         int curP = -1, curQ = -1;
  35.         for(int i = 0; i < n; i++){
  36.             curP = max(curP, p[i]);
  37.             P[i]  = curP;
  38.             curQ = max(curQ, q[i]);
  39.             Q[i]  = curQ;
  40.         }
  41.  
  42.         // 3) Precompute pow2[x] = 2^x mod MOD for x=0..n-1 in O(n)
  43.         vector<int> pow2(n);
  44.         pow2[0] = 1;
  45.         for(int x = 1; x < n; x++){
  46.             pow2[x] = int((2LL * pow2[x-1]) % MOD);
  47.         }
  48.  
  49.         // 4) Now compute each r[i] in O(1) using the 3‐case logic:
  50.         //    r[i] = 2^{M_i} + 2^{m_i}  (mod MOD).
  51.  
  52.         vector<int> ans(n);
  53.         for(int i = 0; i < n; i++){
  54.             int MP = P[i];
  55.             int MQ = Q[i];
  56.             int M  = max(MP, MQ);
  57.  
  58.             int m_i;
  59.             if(MP > MQ){
  60.                 // Case A: M = MP.  The only j that attains max=MP is j0 = posP[MP].
  61.                 int j0 = posP[MP];         // guaranteed j0 <= i
  62.                 m_i = q[i - j0];
  63.             }
  64.             else if(MQ > MP){
  65.                 // Case B: M = MQ.  Only j that attains max=MQ is j0 = i - posQ[MQ].
  66.                 int k0 = posQ[MQ];         // k0 <= i
  67.                 int j0 = i - k0;           // that lies in [0..i]
  68.                 m_i = p[j0];
  69.             }
  70.             else {
  71.                 // Case C: MP == MQ == M.
  72.                 int jP = posP[M];          // <= i
  73.                 int jQ = posQ[M];          // <= i
  74.                 int s1 = q[i - jP];        // “smaller exponent” if p_j=M
  75.                 int s2 = p[i - jQ];        // “smaller exponent” if q_{i-j}=M
  76.                 m_i = max(s1, s2);
  77.             }
  78.  
  79.             // Finally
  80.             long long big  = pow2[M];
  81.             long long small = pow2[m_i];
  82.             ans[i] = int( (big + small) % MOD );
  83.         }
  84.  
  85.         // Print r[0..n-1] on one line:
  86.         for(int i = 0; i < n; i++){
  87.             cout << ans[i] << (i+1 < n ? ' ' : '\n');
  88.         }
  89.     }
  90.  
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3
3
0 2 1
1 2 0
5
0 1 2 3 4
4 3 2 1 0
10
5 8 9 3 4 0 2 7 1 6
9 5 1 4 0 3 2 8 7 6
stdout
copy 
3 6 8
17 18 20 24 32
544 768 1024 544 528 528 516 640 516 768
https://ideone.com/2Nwgdv
language:
C++ (gcc 8.3)
created:
7 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!