Submission #627768

#	Time	Username	Problem	Language	Result	Execution time	Memory
627768		peti1234	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1117 ms	39048 KiB

circuit

#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=val*oszt(si)%mod;
    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 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11