fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. static const ll NEG = -(1LL << 60);
  6. static const int MOD = 998244353;
  7.  
  8. struct Cell {
  9.     ll val;
  10.     int cnt;
  11. };
  12.  
  13. struct Mat {
  14.     Cell a[6][6];
  15. };
  16.  
  17. int n, q;
  18. vector<ll> a;
  19. vector<int> col;
  20. vector<Mat> st;
  21. int sz;
  22.  
  23. int go[3][3];
  24.  
  25. inline int id(int r, int b) {
  26.     return r * 2 + b;
  27. }
  28.  
  29. inline void relax(Cell &x, ll v, int c) {
  30.     if (c == 0) return;
  31.     if (v > x.val) {
  32.         x.val = v;
  33.         x.cnt = c;
  34.     } else if (v == x.val) {
  35.         int nv = x.cnt + c;
  36.         if (nv >= MOD) nv -= MOD;
  37.         x.cnt = nv;
  38.     }
  39. }
  40.  
  41. Mat identity_mat() {
  42.     Mat m;
  43.     for (int i = 0; i < 6; ++i) {
  44.         for (int j = 0; j < 6; ++j) {
  45.             m.a[i][j] = {NEG, 0};
  46.         }
  47.         m.a[i][i] = {0, 1};
  48.     }
  49.     return m;
  50. }
  51.  
  52. Mat leaf_mat(ll val, int c) {
  53.     Mat m;
  54.     for (int i = 0; i < 6; ++i)
  55.         for (int j = 0; j < 6; ++j)
  56.             m.a[i][j] = {NEG, 0};
  57.  
  58.     for (int s = 0; s < 6; ++s) {
  59.         int r = s / 2;
  60.         int b = s % 2;
  61.  
  62.         // skip current position
  63.         relax(m.a[s][id(r, 0)], 0, 1);
  64.  
  65.         // take current position
  66.         if (b == 0) {
  67.             int nr = go[r][c];
  68.             if (nr != -1) {
  69.                 relax(m.a[s][id(nr, 1)], val, 1);
  70.             }
  71.         }
  72.     }
  73.     return m;
  74. }
  75.  
  76. Mat merge_mat(const Mat &L, const Mat &R) {
  77.     Mat res;
  78.     for (int i = 0; i < 6; ++i)
  79.         for (int j = 0; j < 6; ++j)
  80.             res.a[i][j] = {NEG, 0};
  81.  
  82.     for (int i = 0; i < 6; ++i) {
  83.         for (int k = 0; k < 6; ++k) {
  84.             if (L.a[i][k].cnt == 0) continue;
  85.             ll lv = L.a[i][k].val;
  86.             int lc = L.a[i][k].cnt;
  87.             for (int j = 0; j < 6; ++j) {
  88.                 if (R.a[k][j].cnt == 0) continue;
  89.                 ll nv = lv + R.a[k][j].val;
  90.                 int nc = int((1LL * lc * R.a[k][j].cnt) % MOD);
  91.                 relax(res.a[i][j], nv, nc);
  92.             }
  93.         }
  94.     }
  95.     return res;
  96. }
  97.  
  98. void build() {
  99.     for (int i = sz - 1; i >= 1; --i) {
  100.         st[i] = merge_mat(st[i << 1], st[i << 1 | 1]);
  101.     }
  102. }
  103.  
  104. void update(int p, ll val, int c) {
  105.     int idx = sz + p - 1;
  106.     st[idx] = leaf_mat(val, c);
  107.     idx >>= 1;
  108.     while (idx) {
  109.         st[idx] = merge_mat(st[idx << 1], st[idx << 1 | 1]);
  110.         idx >>= 1;
  111.     }
  112. }
  113.  
  114. pair<ll, int> get_answer() {
  115.     const Cell &base = st[1].a[id(0, 0)][0];
  116.     ll best = NEG;
  117.     int ways = 0;
  118.     for (int j = 0; j < 6; ++j) {
  119.         const Cell &x = st[1].a[id(0, 0)][j];
  120.         if (x.cnt == 0) continue;
  121.         if (x.val > best) {
  122.             best = x.val;
  123.             ways = x.cnt;
  124.         } else if (x.val == best) {
  125.             ways += x.cnt;
  126.             if (ways >= MOD) ways -= MOD;
  127.         }
  128.     }
  129.     return {best, ways};
  130. }
  131.  
  132. int main() {
  133.     ios::sync_with_stdio(false);
  134.     cin.tie(nullptr);
  135.  
  136.     go[0][0] = 0;
  137.     go[0][1] = 1;
  138.     go[0][2] = -1;
  139.     go[1][0] = 2;
  140.     go[1][1] = 1;
  141.     go[1][2] = -1;
  142.     go[2][0] = 2;
  143.     go[2][1] = -1;
  144.     go[2][2] = -1;
  145.  
  146.     cin >> n >> q;
  147.     a.assign(n + 1, 0);
  148.     col.assign(n + 1, 0);
  149.  
  150.     for (int i = 1; i <= n; ++i) cin >> a[i];
  151.     for (int i = 1; i <= n; ++i) cin >> col[i];
  152.  
  153.     sz = 1;
  154.     while (sz < n) sz <<= 1;
  155.     st.assign(sz << 1, identity_mat());
  156.  
  157.     for (int i = 1; i <= n; ++i) {
  158.         st[sz + i - 1] = leaf_mat(a[i], col[i]);
  159.     }
  160.     for (int i = n + 1; i <= sz; ++i) {
  161.         st[sz + i - 1] = identity_mat();
  162.     }
  163.     build();
  164.  
  165.     while (q--) {
  166.         int type;
  167.         cin >> type;
  168.         if (type == 1) {
  169.             int x;
  170.             ll y;
  171.             cin >> x >> y;
  172.             a[x] = y;
  173.             update(x, a[x], col[x]);
  174.         } else if (type == 2) {
  175.             int x, y;
  176.             cin >> x >> y;
  177.             col[x] = y;
  178.             update(x, a[x], col[x]);
  179.         } else {
  180.             auto [mx, ways] = get_answer();
  181.             cout << mx << ' ' << ways << '\n';
  182.         }
  183.     }
  184.  
  185.     return 0;
  186. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UexaXa
language:
C++14 (gcc 8.3)
created:
1 day 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!