oj.uz

Submission #635629

# Submission time Handle Problem Language Result Execution time Memory
635629 2022-08-26T14:03:21 Z ruhanhabib39 Digital Circuit (IOI22_circuit) C++17
18 / 100
 1104 ms 11344 KB 
#include "circuit.h"

#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>

namespace ruhan {
   using namespace std;

   const long long MOD = 1e9 + 2022;

   int N, M;
   vector<int> P, A;

   vector<vector<int>> G;

   vector<long long> sub_product;
   vector<int> c;

   long long multiplier;

   struct SegTree {
      vector<int> prop, tree;

      void init () {
         prop.resize(4 * M);
         tree.resize(4 * M);

         build(1, 0, M - 1);
      }

      void build (int cn, int b, int e) {
         if (b == e) {
            tree[cn] = A[b];
            return;
         }

         int m = (b + e) / 2;
         build (2 * cn, b, m);
         build (2 * cn + 1, m + 1, e);

         tree[cn] = tree[2*cn] + tree[2*cn+1];
      }

      void update (int l, int r) {
         update(1, 0, M - 1, l, r, 0);
      }

      void update (int cn, int b, int e, int l, int r, int px) {
         if (r < b || l > e) {
            if (px) {
               prop[cn] ^= 1;
               tree[cn] = e - b + 1 - tree[cn];
            }
            return;
         }

         if (l <= b && e <= r) {
            //cerr << b << " " << e << " " << l << " " << r << " " << px << "\n";
            if (!px) {
               prop[cn] ^= 1;
               tree[cn] = e - b + 1 - tree[cn];
            }
            return;
         }

         px ^= prop[cn];
         prop[cn] = 0;
         int m = (b + e) / 2;
         update(2 * cn, b, m, l, r, px);
         update(2 * cn + 1, m + 1, e, l, r, px);

         tree[cn] = tree[2*cn] + tree[2*cn+1];
      }

      int total() const {
         return tree[1];
      }

   } seg_tree;

   void init45 () {
      seg_tree.init();

      auto ss = vector<long long>(N + M, 1LL);
      for (int u = N - 1; u >= 0; u--) {
         int v = 2 * u + 1;
         ss[u] = ss[v] * sub_product[u] % MOD;
      }

      multiplier = ss[1];
      //cerr << "multiplier = " << multiplier << "\n";
      //cerr << "total = " << seg_tree.total() << "\n";
   }

   void init  (int N_, int M_, vector<int> P_, vector<int> A_) {
      N = N_; M = M_; P = P_; A = A_;

      //cerr << "N = " << N << "\n";
      //cerr << "M = " << M << "\n";
      //cerr << "P = ";
      //for (int x : P) //cerr << x << " ";
      //cerr << "\n";
      //cerr << "A = ";
      //for (int x : A) //cerr << x << " ";
      //cerr << "\n";

      c.resize(N);
      G.resize(N);
      for (int i = N + M - 1; i > 0; i--) {
         ////cerr << i << " " << P[i] << "\n";
         c[P[i]]++;
         G[P[i]].push_back(i);
      }

      sub_product = vector<long long>(N + M, 1);
      for (int i = N - 1; i > 0; i--) {
         sub_product[i] *= c[i];
         sub_product[i] %= MOD;

         sub_product[P[i]] *= sub_product[i];
         sub_product[P[i]] %= MOD;
      }

      init45();
   }


   int subtask123 (int L, int R) {
      ////cerr << "\n\ncpunt_ways(" << L << ", " << R << ")\n";
      for (int i = L - N; i <= R - N; i++) {
         A[i] ^= 1;
      }

      vector<long long> X(N + M, 0LL);
      copy(A.begin(), A.end(), X.begin() + N);

      for (int u = N - 1; u >= 0; u--) {
         vector<vector<long long>> dp(c[u] + 1, vector<long long>(c[u] + 1, 0));

         dp[c[u]][0] = 1;
         for (int i = c[u] - 1; i >= 0; i--) {
            int v = G[u][i];

            long long y = (sub_product[v] + MOD - X[v]) % MOD;

            dp[i][0] = y * dp[i+1][0] % MOD;
            for (int p = 1; p <= c[u]; p++) {
               dp[i][p] = X[v] * dp[i+1][p - 1] + y * dp[i+1][p];
               dp[i][p] %= MOD;
            }
         }

         X[u] = 0;
         for (int p = 1; p <= c[u]; p++) {
            X[u] += p * dp[0][p] % MOD;
            X[u] %= MOD;
         }
         ////cerr << "X[" << u << "] = " << X[u] << "\n";
      }

      return X[0];
   }

   int subtask45 (int L, int R) {
      //cerr << "\n\ncount_ways(" << L << ", " << R << ")\n";
      seg_tree.update(L - N, R - N);
      return (multiplier *  seg_tree.total()) % MOD;
   }
};

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
   ruhan::init(N, M, P, A);
}

int count_ways(int L, int R) {
   //return ruhan::subtask123(L, R);
   return ruhan::subtask45(L, R);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 380 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '930201162'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 380 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '930201162'
15 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 5744 KB Output is correct
2 Correct 863 ms 11344 KB Output is correct
3 Correct 1104 ms 11288 KB Output is correct
4 Correct 940 ms 11304 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 5744 KB Output is correct
2 Correct 863 ms 11344 KB Output is correct
3 Correct 1104 ms 11288 KB Output is correct
4 Correct 940 ms 11304 KB Output is correct
5 Correct 589 ms 5812 KB Output is correct
6 Correct 861 ms 11292 KB Output is correct
7 Correct 994 ms 11344 KB Output is correct
8 Correct 845 ms 11316 KB Output is correct
9 Correct 447 ms 624 KB Output is correct
10 Correct 820 ms 976 KB Output is correct
11 Correct 869 ms 976 KB Output is correct
12 Correct 816 ms 980 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '930201162'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 380 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '930201162'
15 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 380 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '930201162'
15 Halted 0 ms 0 KB -