oj.uz

Submission #1063360

# Submission time Handle Problem Language Result Execution time Memory
1063360 2024-08-17T17:18:12 Z jer033 Digital Circuit (IOI22_circuit) C++17
100 / 100
 803 ms 24512 KB 
#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD =  1'000'002'022;
const ll totient = 497758632;//a^(totient-1) = inv(a)

int n, m;
vector<ll> storage;//When you call the constructor, make sure that everything is reduced modulo MOD
vector<int> a;

ll pow(ll a, ll b)
{
    if (b==0ll)
        return 1;
    ll c = pow(a, b/2ll);
    c = (c*c)%MOD;
    if (((b/2ll)*(2ll)) != b)//b is odd
        c = (c*a)%MOD;
    return c;
}

ll inv(ll a)
{
    return pow(a, totient-1ll);
}

class Lazy{
public:
    int L, R;
    ll total_sum;
    ll active;//MAKE SURE THAT THIS IS ALWAYS ACCURATE
    bool flip;//When I need to flip, I don't need to flip myself, I need to flip my children only
    Lazy* left;
    Lazy* right;

    Lazy()
    {
        L = 0; R = 0;
        total_sum = 0; active = 0; flip = 0;
        left = nullptr; right = nullptr;
    }

    Lazy(int l, int r)
    {
        L = l; R = r;
        flip = 0;
        if (L==R)
        {
            left = nullptr;
            right = nullptr;
            total_sum = storage[L];
            if (a[L] == 1)
                active = total_sum;
            else
                active = 0;
        }
        else
        {
            int mid = (l+r)/2;
            left = new Lazy(l, mid);
            right = new Lazy(mid+1, r);
            total_sum = left->total_sum + right->total_sum;
            active = left->active + right->active;
        }
    }

    void update()
    {
        //assumption: My children could have just updated themselves, and so should I
        if (left!=nullptr)
            active = left->active + right->active;
    }

    void pancake_flip()
    {
        //assumption: this is updated, and I want to update myself
        active = total_sum - active;
        if (flip == 0)
            flip = 1;
        else
            flip = 0;
    }

    void push_down()
    {
        //assumption: this is updated, and I want to update my children
        if (flip == 1)
        {
            flip = 0;
            if (left != nullptr)
            {
                left->pancake_flip();
                right->pancake_flip();
            }
        }
    }

    void range_flip(int range_l, int range_r)
    {
        int intersect_l = max(range_l, L);
        int intersect_r = min(range_r, R);
        if ((intersect_l == L) and (intersect_r==R))
        {
            pancake_flip();
            push_down();
        }
        else if (intersect_l <= intersect_r)
        {
            push_down();
            left->range_flip(range_l, range_r);
            right->range_flip(range_l, range_r);
            update();
        }
    }
};

Lazy circ = Lazy();

struct factor{
public:
    ll mn;
    ll f2;
    ll f223;

    factor()
    {
        mn = 1;
        f2 = 0;
        f223 = 0;
    }

    factor(ll a, ll b, ll c)
    {
        mn = a;
        f2 = b;
        f223 = c;
    }
    
    factor(ll n)
    {
        //call this constructor for the degrees
        f2 = 0;
        f223 = 0;
        while ((n%2)==0)
        {
            n = n/2;
            f2++;
        }
        while ((n%223)==0)
        {
            n = n/223;
            f223++;
        }
        mn = n;
    }

    ll conv()
    {
        ll bb = pow(2ll, f2);
        ll cc = pow(223ll, f223);
        ll ans = (mn*bb)%MOD;
        ans = (ans*cc)%MOD;
        return ans;
    }

};

factor multiply(factor x, factor y)
{
    ll a = (x.mn * y.mn)%MOD;
    ll b = (x.f2 + y.f2);
    ll c = (x.f223 + y.f223);
    factor ans = factor(a, b, c);
    return ans;
}

factor divide(factor x, factor y)
{
    ll d = inv(y.mn);
    factor mult = factor(d, 0ll-y.f2, 0ll-y.f223);
    return multiply(x, mult);
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N;
    m = M;
    vector<ll> degrees(N, 0);
    for (int i=1; i<(N+M); i++)
        degrees[P[i]]++;
    vector<factor> orig(N);
    for (int i=0; i<N; i++)
        orig[i] = factor(degrees[i]);
    vector<factor> prods(N);
    prods[0] = orig[0];
    for (int i=1; i<N; i++)
        prods[i] = multiply(prods[i-1], orig[i]);
    vector<factor> quots(N);
    quots[0] = divide(prods[N-1], orig[0]);
    for (int i=1; i<N; i++)
        quots[i] = divide(quots[P[i]], orig[i]);

    for (int i=N; i<(N+M); i++)
    {
        storage.push_back(quots[P[i]].conv());
    }

    //NOTES: Fill in storage with the appropriate values! Initially it is empty. 
    //MAKE SURE TO REDUCE ALL VALLUES MODULO MOD, THANK YOU!
    a = A;
    circ = Lazy(0, M-1);
}

int count_ways(int L, int R) {
    L -= n;
    R -= n;
    circ.range_flip(L, R);
    ll fa = circ.active%MOD;
    int ffa = fa;
    return ffa;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 600 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 600 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 0 ms 600 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 1 ms 600 KB Output is correct
38 Correct 1 ms 600 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 8148 KB Output is correct
2 Correct 681 ms 16072 KB Output is correct
3 Correct 727 ms 16080 KB Output is correct
4 Correct 672 ms 16080 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 8148 KB Output is correct
2 Correct 681 ms 16072 KB Output is correct
3 Correct 727 ms 16080 KB Output is correct
4 Correct 672 ms 16080 KB Output is correct
5 Correct 518 ms 8144 KB Output is correct
6 Correct 702 ms 16072 KB Output is correct
7 Correct 709 ms 15944 KB Output is correct
8 Correct 707 ms 16072 KB Output is correct
9 Correct 304 ms 856 KB Output is correct
10 Correct 613 ms 1368 KB Output is correct
11 Correct 644 ms 1368 KB Output is correct
12 Correct 642 ms 1368 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 469 ms 8148 KB Output is correct
14 Correct 681 ms 16072 KB Output is correct
15 Correct 727 ms 16080 KB Output is correct
16 Correct 672 ms 16080 KB Output is correct
17 Correct 518 ms 8144 KB Output is correct
18 Correct 702 ms 16072 KB Output is correct
19 Correct 709 ms 15944 KB Output is correct
20 Correct 707 ms 16072 KB Output is correct
21 Correct 304 ms 856 KB Output is correct
22 Correct 613 ms 1368 KB Output is correct
23 Correct 644 ms 1368 KB Output is correct
24 Correct 642 ms 1368 KB Output is correct
25 Correct 717 ms 23720 KB Output is correct
26 Correct 781 ms 24284 KB Output is correct
27 Correct 749 ms 24260 KB Output is correct
28 Correct 582 ms 24216 KB Output is correct
29 Correct 783 ms 24260 KB Output is correct
30 Correct 709 ms 24260 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 600 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 0 ms 600 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 1 ms 600 KB Output is correct
38 Correct 1 ms 600 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 445 ms 856 KB Output is correct
44 Correct 636 ms 1112 KB Output is correct
45 Correct 666 ms 1112 KB Output is correct
46 Correct 617 ms 1624 KB Output is correct
47 Correct 667 ms 1624 KB Output is correct
48 Correct 693 ms 1624 KB Output is correct
49 Correct 652 ms 1620 KB Output is correct
50 Correct 591 ms 1624 KB Output is correct
51 Correct 624 ms 1112 KB Output is correct
52 Correct 670 ms 1112 KB Output is correct
53 Correct 592 ms 856 KB Output is correct
54 Correct 668 ms 1624 KB Output is correct
55 Correct 660 ms 1368 KB Output is correct
56 Correct 658 ms 1112 KB Output is correct
57 Correct 633 ms 1112 KB Output is correct
58 Correct 630 ms 1624 KB Output is correct
59 Correct 658 ms 1624 KB Output is correct
60 Correct 637 ms 1624 KB Output is correct
61 Correct 665 ms 1112 KB Output is correct
62 Correct 630 ms 1112 KB Output is correct
63 Correct 669 ms 1112 KB Output is correct
64 Correct 704 ms 1112 KB Output is correct
65 Correct 287 ms 856 KB Output is correct
66 Correct 646 ms 1368 KB Output is correct
67 Correct 675 ms 1368 KB Output is correct
68 Correct 622 ms 1368 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 600 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 0 ms 600 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 1 ms 600 KB Output is correct
38 Correct 1 ms 600 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 469 ms 8148 KB Output is correct
44 Correct 681 ms 16072 KB Output is correct
45 Correct 727 ms 16080 KB Output is correct
46 Correct 672 ms 16080 KB Output is correct
47 Correct 518 ms 8144 KB Output is correct
48 Correct 702 ms 16072 KB Output is correct
49 Correct 709 ms 15944 KB Output is correct
50 Correct 707 ms 16072 KB Output is correct
51 Correct 304 ms 856 KB Output is correct
52 Correct 613 ms 1368 KB Output is correct
53 Correct 644 ms 1368 KB Output is correct
54 Correct 642 ms 1368 KB Output is correct
55 Correct 717 ms 23720 KB Output is correct
56 Correct 781 ms 24284 KB Output is correct
57 Correct 749 ms 24260 KB Output is correct
58 Correct 582 ms 24216 KB Output is correct
59 Correct 783 ms 24260 KB Output is correct
60 Correct 709 ms 24260 KB Output is correct
61 Correct 445 ms 856 KB Output is correct
62 Correct 636 ms 1112 KB Output is correct
63 Correct 666 ms 1112 KB Output is correct
64 Correct 617 ms 1624 KB Output is correct
65 Correct 667 ms 1624 KB Output is correct
66 Correct 693 ms 1624 KB Output is correct
67 Correct 652 ms 1620 KB Output is correct
68 Correct 591 ms 1624 KB Output is correct
69 Correct 624 ms 1112 KB Output is correct
70 Correct 670 ms 1112 KB Output is correct
71 Correct 592 ms 856 KB Output is correct
72 Correct 668 ms 1624 KB Output is correct
73 Correct 660 ms 1368 KB Output is correct
74 Correct 658 ms 1112 KB Output is correct
75 Correct 633 ms 1112 KB Output is correct
76 Correct 630 ms 1624 KB Output is correct
77 Correct 658 ms 1624 KB Output is correct
78 Correct 637 ms 1624 KB Output is correct
79 Correct 665 ms 1112 KB Output is correct
80 Correct 630 ms 1112 KB Output is correct
81 Correct 669 ms 1112 KB Output is correct
82 Correct 704 ms 1112 KB Output is correct
83 Correct 287 ms 856 KB Output is correct
84 Correct 646 ms 1368 KB Output is correct
85 Correct 675 ms 1368 KB Output is correct
86 Correct 622 ms 1368 KB Output is correct
87 Correct 0 ms 344 KB Output is correct
88 Correct 458 ms 20932 KB Output is correct
89 Correct 728 ms 14536 KB Output is correct
90 Correct 714 ms 14800 KB Output is correct
91 Correct 748 ms 24260 KB Output is correct
92 Correct 784 ms 24260 KB Output is correct
93 Correct 762 ms 24512 KB Output is correct
94 Correct 767 ms 24292 KB Output is correct
95 Correct 677 ms 24260 KB Output is correct
96 Correct 600 ms 15704 KB Output is correct
97 Correct 691 ms 15564 KB Output is correct
98 Correct 582 ms 9044 KB Output is correct
99 Correct 756 ms 24176 KB Output is correct
100 Correct 728 ms 19916 KB Output is correct
101 Correct 684 ms 17604 KB Output is correct
102 Correct 760 ms 15672 KB Output is correct
103 Correct 803 ms 24260 KB Output is correct
104 Correct 741 ms 24260 KB Output is correct
105 Correct 694 ms 24260 KB Output is correct
106 Correct 711 ms 13252 KB Output is correct
107 Correct 699 ms 14096 KB Output is correct
108 Correct 733 ms 14796 KB Output is correct
109 Correct 772 ms 15564 KB Output is correct