oj.uz

Submission #627757

# Submission time Handle Problem Language Result Execution time Memory
627757 2022-08-12T22:20:21 Z peti1234 Digital Circuit (IOI22_circuit) C++17
0 / 100
 32 ms 28172 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+m], sum2[i]=0;
            if (aa[i-po]) flip[i]=1, swap(sum[i], sum2[i]);
        }
    }
    for (int i=po-1; i>=1; i--) {
        bal[i]=bal[2*i], jobb[i]=jobb[2*i+1];
        calc(i);
    }
}
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(x);
}
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;
    while (si%2==0) p2--, si/=2;
    while (si%223) 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) {
    add(1, L, R);
    return sum[1];
}
/*
int main()
{
    return 0;
}
*/

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 24272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 24280 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 24272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 28172 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 28172 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 24280 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 24272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 24272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -