oj.uz

Submission #1024571

# Submission time Handle Problem Language Result Execution time Memory
1024571 2024-07-16T08:07:34 Z Wansur Digital Circuit (IOI22_circuit) C++17
0 / 100
 462 ms 13144 KB 
#include <bits/stdc++.h>
#define ent '\n'
#define f first
#define s second

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 12;
const int mod = 1e9 + 2022;

pair<ll, ll> t[maxn];
vector<int> g[maxn];
int p[maxn];
int a[maxn];
int n, m;

pair<ll, ll> merge(pair<ll, ll> a, pair<ll, ll> b){
    pair<ll, ll> ans = {0, 0};
    ans.f += a.f * b.f * 2 + a.f * b.s + a.s * b.f;
    ans.s += a.s * b.s * 2 + a.f * b.s + a.s * b.f;
    ans.f %= mod, ans.s %= mod;
    return ans;
}

void build(int v, int tl, int tr){
    p[v] = 0;
    if(tl == tr){
        if(a[tl]) t[v] = {0, 1};
        else t[v] = {1, 0};
    }
    else{
        int mid = tl + tr >> 1;
        build(v*2, tl, mid);
        build(v*2+1, mid+1, tr);
        t[v] = merge(t[v*2], t[v*2+1]);
    }
}

void push(int v, int tl, int tr){
    if(tl == tr || !p[v]){
        return;
    }
    p[v*2] ^= 1;
    p[v*2+1] ^= 1;
    swap(t[v*2].f, t[v*2].s);
    swap(t[v*2+1].f, t[v*2+1].s);
    p[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r){
    push(v, tl, tr);
    if(tl > r || l > tr){
        return;
    }
    if(tl >= l && tr <= r){
        swap(t[v].f, t[v].s);
        p[v] = 1;
        return;
    }
    int mid = tl + tr >> 1;
    upd(v*2, tl, mid, l, r);
    upd(v*2+1, mid+1, tr, l, r);
    t[v] = merge(t[v*2], t[v*2+1]);
}

void init(int N, int M, std::vector<int> P, std::vector<int> A){
    n = M, m = N;
    for(int i=1;i<=n;i++){
        a[i] = A[i-1];
    }
    build(1, 1, n);
}

int count_ways(int L, int R){
    L -= m - 1;
    R -= m - 1;
    upd(1, 1, n, L, R);
    return t[1].s;
}

Compilation message

circuit.cpp: In function 'void build(int, int, int)':
circuit.cpp:32:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~
circuit.cpp: In function 'void upd(int, int, int, int, int)':
circuit.cpp:60:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid = tl + tr >> 1;
      |               ~~~^~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 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 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Incorrect 1 ms 4440 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 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 KB 1st lines differ - on the 1st token, expected: '509', found: '159879670'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 5208 KB Output is correct
2 Runtime error 17 ms 13144 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 5208 KB Output is correct
2 Runtime error 17 ms 13144 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Incorrect 1 ms 4440 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 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 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 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 KB 1st lines differ - on the 1st token, expected: '509', found: '159879670'
4 Halted 0 ms 0 KB -