oj.uz

Submission #627765

# Submission time Handle Problem Language Result Execution time Memory
627765 2022-08-12T22:34:50 Z peti1234 Digital Circuit (IOI22_circuit) C++17
52 / 100
 1059 ms 38472 KB 
#include <bits/stdc++.h>

using namespace std;
//#include "circuit.h"
const int c=500005;
int n, m;
const long long mod=1000002022, phimod=497758632;
int bal[c], jobb[c];
long long ert[c], sum[c], sum2[c], flip[c], po2[c], po223[c], rem[c];
vector<int> sz[c], aa;
long long po(long long a, long long p) {
    long long ans=1;
    while (p) {
        if (p%2) ans=ans*a%mod;
        a=a*a%mod;
        p/=2;
    }
    return ans;
}
long long oszt(long long a) {
    assert(__gcd(mod, a)==1);
    return po(a, phimod-1);
}
void calc(int a) {
    int x=2*a, y=2*a+1;
    sum[a]=(sum[x]+sum[y])%mod;
    sum2[a]=(sum2[x]+sum2[y])%mod;
    if (flip[a]) {
        swap(sum[a], sum2[a]);
    }
}
void seg_tree_init(int m) {
    int po=1;
    while (po<m) {
        po*=2;
    }
    for (int i=po; i<2*po; i++) {
        bal[i]=i-po, jobb[i]=i-po;
        if (i-po<m) {
            sum[i]=ert[i-po+n], sum2[i]=0;
            if (!aa[i-po]) flip[i]=1, swap(sum[i], sum2[i]);
            //cout << "fontos " << i << " " << sum[i] << " " << sum2[i] << "\n";
        }
    }
    for (int i=po-1; i>=1; i--) {
        bal[i]=bal[2*i], jobb[i]=jobb[2*i+1];
        calc(i);
        //cout << "kozep " << i << " " << sum[i] << " " << sum2[i] << "\n";
    }
}
int h(int a, int l, int r) {
    if (bal[a]>r || jobb[a]<l) return 0;
    if (l<=bal[a] && jobb[a]<=r) return 2;
    return 1;
}
void add(int a, int l, int r) {
    int s=h(a, l, r);
    if (s==0) return;
    if (s==2) {
        flip[a]=1-flip[a];
        swap(sum[a], sum2[a]);
        return;
    }
    int x=2*a, y=2*a+1;
    add(x, l, r), add(y, l, r);
    calc(a);
}
void dfs(int a) {
    int si=sz[a].size();
    long long p2=po2[a], p223=po223[a], val=rem[a];
    ert[a]=po(2, p2)*po(223, p223)%mod*val%mod;
    //cout << "dfs " << a << " " << ert[a] << "\n";
    if (si==0) return;
    while (si%2==0) p2--, si/=2;
    while (si%223==0) p223--, si/=223;
    val*=oszt(si);
    for (auto x:sz[a]) {
        po2[x]=p2, po223[x]=p223, rem[x]=val;
        dfs(x);
    }
}
void init(int N, int M, vector<int> P, vector<int> A) {
    n=N, m=M;
    aa=A;
    for (int i=1; i<n+m; i++) {
        sz[P[i]].push_back(i);
    }
    rem[0]=1;
    for (int i=0; i<n; i++) {
        int si=sz[i].size();
        while (si%2==0) po2[0]++, si/=2;
        while (si%223==0) po223[0]++, si/=223;
        rem[0]=rem[0]*si%mod;
    }
    dfs(0);
    seg_tree_init(m);
}

int count_ways(int L, int R) {
    L-=n, R-=n;
    add(1, L, R);
    return sum[1];
}
/*
int main()
{
    int a, b;
    vector<int> x, y;
    cin >> a >> b;
    for (int i=0; i<a+b; i++) {
        int s;
        cin >> s;
        x.push_back(s);
    }
    for (int i=0; i<b; i++) {
        int s;
        cin >> s;
        y.push_back(s);
    }
    init(a, b, x, y);
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << count_ways(l, r) << "\n";
    }
    return 0;
}
*/
/*
3 4
-1 0 1 2 1 1 0
1 0 1 0
2
3 4
4 5
*/

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12112 KB Output is correct
2 Correct 7 ms 12048 KB Output is correct
3 Correct 6 ms 12112 KB Output is correct
4 Correct 7 ms 12112 KB Output is correct
5 Correct 6 ms 12112 KB Output is correct
6 Correct 8 ms 12240 KB Output is correct
7 Correct 7 ms 12240 KB Output is correct
8 Correct 7 ms 12240 KB Output is correct
9 Correct 7 ms 12240 KB Output is correct
10 Correct 7 ms 12240 KB Output is correct
11 Correct 7 ms 12240 KB Output is correct
12 Correct 7 ms 12180 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12112 KB Output is correct
2 Correct 6 ms 12112 KB Output is correct
3 Correct 7 ms 12368 KB Output is correct
4 Correct 7 ms 12112 KB Output is correct
5 Correct 6 ms 12112 KB Output is correct
6 Correct 6 ms 12240 KB Output is correct
7 Correct 7 ms 12112 KB Output is correct
8 Correct 6 ms 12112 KB Output is correct
9 Correct 7 ms 12112 KB Output is correct
10 Correct 7 ms 12048 KB Output is correct
11 Correct 6 ms 12112 KB Output is correct
12 Correct 7 ms 12112 KB Output is correct
13 Correct 6 ms 12112 KB Output is correct
14 Correct 8 ms 12240 KB Output is correct
15 Correct 7 ms 12240 KB Output is correct
16 Correct 7 ms 12240 KB Output is correct
17 Correct 7 ms 12240 KB Output is correct
18 Correct 7 ms 12240 KB Output is correct
19 Correct 7 ms 12240 KB Output is correct
20 Correct 7 ms 12180 KB Output is correct
21 Incorrect 7 ms 12240 KB 1st lines differ - on the 1st token, expected: '759476520', found: '-299242784'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 17796 KB Output is correct
2 Correct 887 ms 23604 KB Output is correct
3 Correct 863 ms 23044 KB Output is correct
4 Correct 968 ms 23576 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 17796 KB Output is correct
2 Correct 887 ms 23604 KB Output is correct
3 Correct 863 ms 23044 KB Output is correct
4 Correct 968 ms 23576 KB Output is correct
5 Correct 678 ms 17856 KB Output is correct
6 Correct 914 ms 23624 KB Output is correct
7 Correct 976 ms 23624 KB Output is correct
8 Correct 1008 ms 23544 KB Output is correct
9 Correct 413 ms 12368 KB Output is correct
10 Correct 848 ms 12864 KB Output is correct
11 Correct 875 ms 12752 KB Output is correct
12 Correct 771 ms 12740 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12112 KB Output is correct
2 Correct 7 ms 12048 KB Output is correct
3 Correct 6 ms 12112 KB Output is correct
4 Correct 7 ms 12112 KB Output is correct
5 Correct 6 ms 12112 KB Output is correct
6 Correct 8 ms 12240 KB Output is correct
7 Correct 7 ms 12240 KB Output is correct
8 Correct 7 ms 12240 KB Output is correct
9 Correct 7 ms 12240 KB Output is correct
10 Correct 7 ms 12240 KB Output is correct
11 Correct 7 ms 12240 KB Output is correct
12 Correct 7 ms 12180 KB Output is correct
13 Correct 517 ms 17796 KB Output is correct
14 Correct 887 ms 23604 KB Output is correct
15 Correct 863 ms 23044 KB Output is correct
16 Correct 968 ms 23576 KB Output is correct
17 Correct 678 ms 17856 KB Output is correct
18 Correct 914 ms 23624 KB Output is correct
19 Correct 976 ms 23624 KB Output is correct
20 Correct 1008 ms 23544 KB Output is correct
21 Correct 413 ms 12368 KB Output is correct
22 Correct 848 ms 12864 KB Output is correct
23 Correct 875 ms 12752 KB Output is correct
24 Correct 771 ms 12740 KB Output is correct
25 Correct 878 ms 30464 KB Output is correct
26 Correct 1059 ms 30584 KB Output is correct
27 Correct 1044 ms 30624 KB Output is correct
28 Correct 787 ms 30708 KB Output is correct
29 Correct 953 ms 38472 KB Output is correct
30 Correct 896 ms 38392 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12112 KB Output is correct
2 Correct 6 ms 12112 KB Output is correct
3 Correct 7 ms 12368 KB Output is correct
4 Correct 7 ms 12112 KB Output is correct
5 Correct 6 ms 12112 KB Output is correct
6 Correct 6 ms 12240 KB Output is correct
7 Correct 7 ms 12112 KB Output is correct
8 Correct 6 ms 12112 KB Output is correct
9 Correct 7 ms 12112 KB Output is correct
10 Correct 7 ms 12048 KB Output is correct
11 Correct 6 ms 12112 KB Output is correct
12 Correct 7 ms 12112 KB Output is correct
13 Correct 6 ms 12112 KB Output is correct
14 Correct 8 ms 12240 KB Output is correct
15 Correct 7 ms 12240 KB Output is correct
16 Correct 7 ms 12240 KB Output is correct
17 Correct 7 ms 12240 KB Output is correct
18 Correct 7 ms 12240 KB Output is correct
19 Correct 7 ms 12240 KB Output is correct
20 Correct 7 ms 12180 KB Output is correct
21 Incorrect 7 ms 12240 KB 1st lines differ - on the 1st token, expected: '759476520', found: '-299242784'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12112 KB Output is correct
2 Correct 6 ms 12112 KB Output is correct
3 Correct 7 ms 12368 KB Output is correct
4 Correct 7 ms 12112 KB Output is correct
5 Correct 6 ms 12112 KB Output is correct
6 Correct 6 ms 12240 KB Output is correct
7 Correct 7 ms 12112 KB Output is correct
8 Correct 6 ms 12112 KB Output is correct
9 Correct 7 ms 12112 KB Output is correct
10 Correct 7 ms 12048 KB Output is correct
11 Correct 6 ms 12112 KB Output is correct
12 Correct 7 ms 12112 KB Output is correct
13 Correct 6 ms 12112 KB Output is correct
14 Correct 8 ms 12240 KB Output is correct
15 Correct 7 ms 12240 KB Output is correct
16 Correct 7 ms 12240 KB Output is correct
17 Correct 7 ms 12240 KB Output is correct
18 Correct 7 ms 12240 KB Output is correct
19 Correct 7 ms 12240 KB Output is correct
20 Correct 7 ms 12180 KB Output is correct
21 Incorrect 7 ms 12240 KB 1st lines differ - on the 1st token, expected: '759476520', found: '-299242784'
22 Halted 0 ms 0 KB -