oj.uz

Submission #1058481

# Submission time Handle Problem Language Result Execution time Memory
1058481 2024-08-14T10:13:22 Z mychecksedad Digital Circuit (IOI22_circuit) C++17
16 / 100
 624 ms 23384 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define en cout << '\n'
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define vi vector<int>
#define ll long long int
#define ff first
#define ss second
const int N = 500000+10;
const ll MOD = 1000002022;
int n, m;
vector<int> g[N];
array<ll, 4> T[N];
vi val;
int lazy[N];
int F;
array<ll, 4> comb(array<ll, 4> x, array<ll, 4> y){
  array<ll, 4> z;
  z[0] = (x[0] * y[0] + x[0] * y[0] + x[0] * y[1] + x[1] * y[0]) % MOD;
  z[1] = (x[0] * y[1] + x[1] * y[0] + x[1] * y[1] + x[1] * y[1]) % MOD;
  z[2] = (x[2] * y[2] + x[2] * y[2] + x[2] * y[3] + x[3] * y[2]) % MOD;
  z[3] = (x[2] * y[3] + x[3] * y[2] + x[3] * y[3] + x[3] * y[3]) % MOD;
  // cout << z[3] << ' ';
  return z;
}
void build(int l, int r, int k){
  lazy[k] = 0;
  if(l == r){
    T[k] = {
      1-val[l],
      val[l],
      val[l],
      1-val[l]
    };
    // cout << val[l] << 'f';
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  T[k] = comb(T[k<<1], T[k<<1|1]);
}
int get(){
  // cout << T[1][0] << ' ' << T[1][1] << ' ' << T[1][2] << ' ' << T[1][3] << '\n';
  return T[1][1];
}
void push(int k){
  if(lazy[k]){
    lazy[k<<1] ^= lazy[k];
    lazy[k<<1|1] ^= lazy[k];
    swap(T[k<<1][0], T[k<<1][2]);
    swap(T[k<<1][1], T[k<<1][3]);
    swap(T[k<<1|1][0], T[k<<1|1][2]);
    swap(T[k<<1|1][1], T[k<<1|1][3]);
    lazy[k] = 0;
  }
}
void upd(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    swap(T[k][0], T[k][2]);
    swap(T[k][1], T[k][3]);
    lazy[k] ^= 1;
    return;
  }
  push(k);
  int m = l+r>>1;
  upd(l, m, ql, qr, k<<1);
  upd(m+1, r, ql, qr, k<<1|1);
  T[k] = comb(T[k<<1], T[k<<1|1]);
}
void init(int nn, int mm, std::vector<int> P, std::vector<int> A) { n=nn, m=mm;
  for(int i = 1; i < n + m; ++i) g[P[i]].pb(i);
  val = A;
  build(0, m - 1, 1);
}

int count_ways(int L, int R) {
  L -= n, R -= n;
  upd(0, m - 1, L, R, 1);
  return get();
}

Compilation message

circuit.cpp: In function 'void build(int, int, int)':
circuit.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int m = l+r>>1;
      |           ~^~
circuit.cpp: In function 'void upd(int, int, int, int, int)':
circuit.cpp:70:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |   int m = l+r>>1;
      |           ~^~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 19288 KB Output is correct
2 Correct 619 ms 23384 KB Output is correct
3 Correct 560 ms 23384 KB Output is correct
4 Correct 595 ms 23384 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 19288 KB Output is correct
2 Correct 619 ms 23384 KB Output is correct
3 Correct 560 ms 23384 KB Output is correct
4 Correct 595 ms 23384 KB Output is correct
5 Correct 485 ms 19288 KB Output is correct
6 Correct 624 ms 23384 KB Output is correct
7 Correct 589 ms 23384 KB Output is correct
8 Correct 572 ms 23384 KB Output is correct
9 Correct 272 ms 15192 KB Output is correct
10 Correct 602 ms 15448 KB Output is correct
11 Correct 566 ms 15444 KB Output is correct
12 Correct 543 ms 15448 KB Output is correct

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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