fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int Mod= 998244353;
  5. const ll INF = 10000000000000;
  6. const int N = 1e6+7;
  7.  
  8.     void solve() {
  9.         int n;
  10.         cin >> n;
  11.         vector<int> pow2(n);
  12.         pow2[0]=1;
  13.         for(int i=1;i<n;i++)  pow2[i]=(int)(2LL*pow2[i-1]%Mod)%Mod;
  14.         vector<int> p(n), q(n);
  15.         for(int i = 0; i < n; i++) cin >> p[i];
  16.         for(int i = 0; i < n; i++) cin >> q[i];
  17.         vector<int> Ppos(n), Qpos(n);
  18.         for(int i = 0; i < n; i++){
  19.             Ppos[p[i]] = i;
  20.             Qpos[q[i]] = i;
  21.         }
  22.         vector<int> mxP(n),mxQ(n);
  23.         int currp , currq;
  24.         currp = currq = -1;
  25.         for(int i=0;i<n;i++){
  26.             currp=max(currp,p[i]);
  27.             mxP[i]=currp;
  28.             currq=max(currq,q[i]);
  29.             mxQ[i]=currq;
  30.         }
  31.         vector<int> r(n);
  32.         int mi;
  33.         for(int i=0;i<n;i++){
  34.             int n1 = mxP[i];
  35.             int n2 = mxQ[i];
  36.             int N = max(n1,n2);
  37.             if(n1>n2){
  38.                int j = Ppos[n1];
  39.                mi = q[i-j]; 
  40.             }
  41.             else if(n2>n1){
  42.                 int j = Qpos[n2];
  43.                 mi= p[i-j];
  44.             }
  45.             else{
  46.                int j1=Ppos[n1];
  47.                int j2=Qpos[n2];
  48.                mi=max(p[i-j2],q[i-j1]); 
  49.             }
  50.             r[i]=(pow2[N]+pow2[mi])%Mod;
  51.         }
  52.         for(int i=0;i<n;i++) cout << r[i] << " ";
  53.         cout << '\n';
  54.     }
  55. int main(){ 
  56.     ios::sync_with_stdio(false);
  57.     cin.tie(nullptr);
  58.  
  59.     int t;
  60.     cin >> t;
  61.     while (t--) solve();
  62.  
  63.     return 0;
  64. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
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 
3 6 8 
17 18 20 24 32 
544 768 1024 544 528 528 516 640 516 768
https://ideone.com/gNds68
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!