oj.uz

Submission #807554

# Submission time Handle Problem Language Result Execution time Memory
807554 2023-08-04T19:19:49 Z Ozy Digital Circuit (IOI22_circuit) C++17
16 / 100
 844 ms 4944 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 - 2);
  R -= (offset - 2);
  update(1,1,offset,L,R);

  return stree[1].unos;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 208 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: '0'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 2512 KB Output is correct
2 Correct 844 ms 4904 KB Output is correct
3 Correct 700 ms 4816 KB Output is correct
4 Correct 393 ms 4944 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 2512 KB Output is correct
2 Correct 844 ms 4904 KB Output is correct
3 Correct 700 ms 4816 KB Output is correct
4 Correct 393 ms 4944 KB Output is correct
5 Correct 527 ms 2604 KB Output is correct
6 Correct 820 ms 4920 KB Output is correct
7 Correct 672 ms 4816 KB Output is correct
8 Correct 740 ms 4808 KB Output is correct
9 Correct 318 ms 336 KB Output is correct
10 Correct 658 ms 592 KB Output is correct
11 Correct 758 ms 464 KB Output is correct
12 Correct 761 ms 592 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 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 208 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: '0'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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