Submission #635631

#	Time	Username	Problem	Language	Result	Execution time	Memory
635631		ruhanhabib39	Digital Circuit (IOI22_circuit)	C++17	34 / 100	923 ms	16796 KiB

circuit

#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;

   int Q = 0;

   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);
   ruhan::Q++;

   if (ruhan::N <= 1000 && ruhan::M <= 1000 && ruhan::Q <= 5) return ruhan::subtask123(L, R);
   else return ruhan::subtask45(L, R);
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11