oj.uz

Submission #807551

# Submission time Handle Problem Language Result Execution time Memory
807551 2023-08-04T19:17:12 Z Ozy Digital Circuit (IOI22_circuit) C++17
0 / 100
 422 ms 2600 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 200000
#define mod 1000002022

struct x {
  lli unos;
  lli ceros;
  lli lazy;
};

x stree[MAX+2];
lli offset;

void push(lli pos){
  if (!stree[pos].lazy) return;

  swap(stree[pos].ceros, stree[pos].unos);
  if (pos < offset) {
    stree[pos*2].lazy ^= 1;
    stree[(pos*2)+1].lazy ^= 1;
  }

  stree[pos].lazy = 0;
  return;
}

x solve(x a, x b) {
  x res;

  res.ceros = a.ceros*b.ceros*2;
  res.unos = a.unos*b.unos*2;

  lli y = a.ceros*b.unos + b.ceros*a.unos;
  res.ceros += y;
  res.unos += y;
  
  res.ceros %= mod;
  res.unos %= mod;

  return res;
}

void update(lli pos, lli ini, lli fin, lli l, lli r) {
  push(pos);
  if(ini > r || fin < l) return;
  if (l <= ini && fin <= r) {
    stree[pos].lazy = 1;
    push(pos);
    return;
  }

  lli mitad = (ini+fin)/2;
  update(pos*2,ini,mitad,l,r);
  update(pos*2+1,mitad+1,fin,l,r);

  stree[pos] = solve(stree[pos*2], stree[pos*2+1]);
  return;
}

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

  offset = 1;
  while (offset < M) offset *= 2;

  rep(i,offset,offset+M-1) {
    if  (A[i-offset] == 1) stree[i] = {1,0};
    else stree[i] = {0,1}; 
  }
  repa(pos,offset-1,1) stree[pos] = solve(stree[pos*2], stree[pos*2+1]);
}

int count_ways(int L, int R) {
  L -= (offset - 1);
  R -= (offset - 1);
  update(1,1,offset,L,R);

  return stree[1].unos;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 422 ms 2600 KB 4th lines differ - on the 1st token, expected: '469385826', found: '394586018'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 422 ms 2600 KB 4th lines differ - on the 1st token, expected: '469385826', found: '394586018'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -