Submission #1234049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234049		trimkus	Digital Circuit (IOI22_circuit)	C++20	0 / 100	186 ms	1852 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022;
const int MAXN = 2e5 + 5;
int A[MAXN + 1];
int N, M;
int cnt1[MAXN], cnth[MAXN], cnt0[MAXN];
ll M2;
void update(int i, int l, int r, int ql, int qr, bool add = false) {
  // cout << l << " " << r << " " << ql << " " << qr << "\n";
  if (ql > r || l > qr) return;
  if (ql <= l && r <= qr) {
    int tmp = cnt0[i];
    cnt0[i] = cnt1[i];
    cnt1[i] = tmp; 
    if (add) { 
      // cout << l << " " << r << " = " << A[l] << "\n";

      if (A[l]) cnt1[i] += 1;
      else cnt0[i] += 1;
    }
    return;
  }
  int m = (l + r) / 2;
  update(i * 2, l, m, ql, qr, add);
  update(i * 2 + 1, m + 1, r, ql, qr, add);
  cnt0[i] = cnt0[i * 2] + cnt0[i * 2 + 1];
  cnt1[i] = cnt1[i * 2] + cnt1[i * 2 + 1];
}




void init(int _N, int _M, std::vector<int> P, std::vector<int> _A) {
  N = _N;
  M = _M;
  for (int i = N; i < N + M; ++i) {
    A[i + 1] = _A[i - N];
    update(1, 1, N + M, i + 1, i + 1, true);
  }
  M2 = (M / 2) * M % MOD;
  // cout << cnt1[1] << "\n";
}



int count_ways(int L, int R) {
    L += 1;
    R += 1;
    update(1, 1, N + M, L, R);
    int tot = cnt1[1];
    return (tot * M % MOD * M2) % MOD;
}

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