oj.uz

Submission #794552

# Submission time Handle Problem Language Result Execution time Memory
794552 2023-07-26T15:42:52 Z adrilen Digital Circuit (IOI22_circuit) C++17
2 / 100
 563 ms 10392 KB 
#include "circuit.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<ll, 2>;
using arrr = array<int, 3>;

constexpr ll mod = 1e9 + 2022;
constexpr int maxn = 2e5;

void fmod(ll &val)
{
    if (val >= mod) val %= mod;
}

int n, m;
basic_string <int> children[maxn];


ll max_val = 1;

ll vals[maxn] = { 0 };


void dfs(int p, ll v)
{
    if (!children[p].empty()) vals[p] = v * children[p].size(), max_val *= children[p].size();
    else vals[p] = v;

    fmod(vals[p]);
    fmod(max_val);

    for (int i : children[p]) dfs(i, vals[p]);
}



constexpr int siz = 1 << 17;

arr segtree[siz * 2] = { 0 };
bool flipped[siz * 2] = { 0 };

arr merge(arr ap, arr bp)
{
    ap[0] += bp[0], ap[1] += bp[1];
    fmod(ap[0]), fmod(ap[1]);
    return ap;
}

void print()
{
    for (int i = 1; i < 2 * siz; i++)
    {
        if (__builtin_popcount(i) == 1) cout << "\n";
        cout << segtree[i][0] << " ";
    }
    cout << endl;
}


void init(int N, int M, std::vector<int> p, std::vector<int> a) {
    n = N, m = M;

    for (int i = 1; i < n + m; i++)
    {
        children[p[i]].push_back(i);
    }

    dfs(0, 1);

    for (int i = 0; i < m; i++)
    {
        segtree[i + siz][1] = max_val / vals[i + n]; // Doesn't work with modulo
        if (a[i]) segtree[i + siz][0] = segtree[i + siz][1]; 
    }

    for (int i = siz - 1; i > 0; i--)
    {
        segtree[i] = merge(segtree[i * 2], segtree[i * 2 + 1]);
    }

}

void update(int p, int sl, int sr, int gl, int gr)
{
    if (flipped[p])
    {
        segtree[p][0] = segtree[p][1] - segtree[p][0];
        if (segtree[p][0] < 0) segtree[p][0] += mod;
        

        if (p < siz) flipped[p * 2] ^= 1, flipped[p * 2 + 1] ^= 1;
        flipped[p] ^= 1;
    }

    // cout << p << " " << sl << " " << sr << " " << gl << " " << gr << " \n";

    if (gl <= sl && sr <= gr) {
        segtree[p][0] = segtree[p][1] - segtree[p][0];
        if (segtree[p][0] < 0) segtree[p][0] += mod;


        if (p < siz) flipped[p * 2] ^= 1, flipped[p * 2 + 1] ^= 1;

        return ;
    }


    if (gl > sr || sl > gr) return ;

    int mid = (sl + sr) >> 1;

    update(p * 2, sl, mid, gl, gr);
    update(p * 2 + 1, mid + 1, sr, gl, gr);

    segtree[p] = merge(segtree[p * 2], segtree[p * 2 + 1]);
}



int count_ways(int L, int R) {
    update(1, 0, siz - 1, L - n, R - n);

    // print();

    return segtree[1][0];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8636 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct
3 Correct 6 ms 8632 KB Output is correct
4 Correct 4 ms 8656 KB Output is correct
5 Correct 4 ms 8656 KB Output is correct
6 Correct 4 ms 8656 KB Output is correct
7 Correct 4 ms 8656 KB Output is correct
8 Correct 4 ms 8640 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8636 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct
3 Correct 6 ms 8632 KB Output is correct
4 Correct 4 ms 8656 KB Output is correct
5 Correct 4 ms 8656 KB Output is correct
6 Correct 4 ms 8656 KB Output is correct
7 Correct 4 ms 8656 KB Output is correct
8 Correct 4 ms 8640 KB Output is correct
9 Correct 4 ms 8528 KB Output is correct
10 Incorrect 6 ms 8652 KB 1st lines differ - on the 1st token, expected: '52130940', found: '52130816'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8636 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct
3 Correct 6 ms 8632 KB Output is correct
4 Correct 4 ms 8656 KB Output is correct
5 Correct 4 ms 8656 KB Output is correct
6 Correct 4 ms 8656 KB Output is correct
7 Correct 4 ms 8656 KB Output is correct
8 Correct 4 ms 8640 KB Output is correct
9 Correct 4 ms 8528 KB Output is correct
10 Incorrect 6 ms 8652 KB 1st lines differ - on the 1st token, expected: '52130940', found: '52130816'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8636 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct
3 Correct 6 ms 8632 KB Output is correct
4 Correct 4 ms 8656 KB Output is correct
5 Correct 4 ms 8656 KB Output is correct
6 Correct 4 ms 8656 KB Output is correct
7 Correct 4 ms 8656 KB Output is correct
8 Correct 4 ms 8640 KB Output is correct
9 Correct 4 ms 8528 KB Output is correct
10 Incorrect 6 ms 8652 KB 1st lines differ - on the 1st token, expected: '52130940', found: '52130816'
11 Halted 0 ms 0 KB -