oj.uz

Submission #1024572

# Submission time Handle Problem Language Result Execution time Memory
1024572 2024-07-16T08:08:22 Z vjudge1 Digital Circuit (IOI22_circuit) C++17
16 / 100
 722 ms 10328 KB 
#include <bits/stdc++.h>
#define ent '\n'
#define f first
#define s second

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

pair<ll, ll> t[maxn*4];
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 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Incorrect 1 ms 6488 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 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6584 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Incorrect 1 ms 6488 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 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Incorrect 1 ms 6488 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 487 ms 9560 KB Output is correct
2 Correct 688 ms 10328 KB Output is correct
3 Correct 649 ms 10328 KB Output is correct
4 Correct 659 ms 10200 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 9560 KB Output is correct
2 Correct 688 ms 10328 KB Output is correct
3 Correct 649 ms 10328 KB Output is correct
4 Correct 659 ms 10200 KB Output is correct
5 Correct 558 ms 9560 KB Output is correct
6 Correct 722 ms 10328 KB Output is correct
7 Correct 686 ms 10328 KB Output is correct
8 Correct 640 ms 10328 KB Output is correct
9 Correct 311 ms 6488 KB Output is correct
10 Correct 645 ms 8536 KB Output is correct
11 Correct 638 ms 8536 KB Output is correct
12 Correct 627 ms 8536 KB Output is correct

Subtask #6
0 / 27.0

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