Submission #1070364

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1070364	2024-08-22T13:40:19 Z	Mihailo	Digital Circuit (IOI22_circuit)	C++17	4 / 100	777 ms	19904 KB

circuit

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pll pair<long long, long long>
#define MOD 1000002022ll
#define xx first
#define yy second
using namespace std;
typedef long long ll;

struct node {
    ll l, r, sum;
    bool flip;
    node *left, *right;
    node(ll l, ll r): l(l), r(r), sum(0), flip(false), left(nullptr), right(nullptr) {};
};

vector<ll> p, prd, w, cmw, makew;
vector<vector<ll>> ch;
ll pref[200200], n;
node *tree;

ll zbir(ll l, ll r) {
    return (pref[r]-(l==0?0:pref[l-1])+MOD)%MOD;
}

void flip(node *cur) {
    if(cur==nullptr) return;
    cur->flip=!cur->flip;
    cur->sum=zbir(cur->l, cur->r)-cur->sum;
}

void flipprop(node *cur) {
    if(cur->flip) {
        cur->flip=false;
        flip(cur->left);
        flip(cur->right);
    }
}

void fix(node *cur) {
    if(cur->l!=cur->r) {
        flipprop(cur->left);
        flipprop(cur->right);
        cur->sum=(cur->left->sum+cur->right->sum)%MOD;
    }
}

node *build(ll l, ll r) {
    node *cur=new node(l, r);
    if(l!=r) {
        ll m=(l+r)/2;
        cur->left=build(l, m);
        cur->right=build(m+1, r);
    }
    return cur;
}

void flipi(node *cur, ll l, ll r) {
    //cout<<l<<' '<<r<<"   "<<cur->l<<' '<<cur->r<<'\n';
    if(l>r) return;
    if(cur->l==l&&cur->r==r) {
        flip(cur);
        return;
    }
    flipi(cur->left, l, min(r, cur->left->r));
    flipi(cur->right, max(l, cur->right->l), r);
    fix(cur);
    //cout<<cur->l<<' '<<cur->r<<' '<<cur->sum<<'\n';
}

ll saberisve() {
    return tree->sum;
}

void solvew(ll l, ll r, ll mul) {
    if(l>r) exit(-1);
    if(l!=r) {
        ll m=(l+r)/2;
        ll nml=mul;
        for(ll i=l; i<=m; i++) {
            nml*=prd[makew[i]];
            nml%=MOD;
        }
        solvew(m+1, r, nml);
        nml=mul;
        for(ll i=m+1; i<=r; i++) {
            nml*=prd[makew[i]];
            nml%=MOD;
        }
        solvew(l, m, nml);
        return;
    }
    w[makew[l]]=mul;
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n=N;
    for(auto i:P) ch.pb(p);
    for(auto i:P) {
        p.pb(i);
        if(i>=0) ch[i].pb(p.size()-1);
        prd.pb(1);
        w.pb(1);
        cmw.pb(1);
    }
    for(ll i=N-1; i>=0; i--) {
        prd[i]=ch[i].size();
        for(ll j:ch[i]) {
            prd[i]*=prd[j];
            prd[i]%=MOD;
        }
    }
    for(ll i=N-1; i>=0; i--) {
        makew=ch[i];
        solvew(0, makew.size()-1, 1);
    }
    for(int i=1; i<N+M; i++) {
        cmw[i]=w[i]*cmw[p[i]];
        cmw[i]%=MOD;
    }
    pref[0]=cmw[N];
    for(int i=1; i<M; i++) {
        pref[i]=pref[i-1]+cmw[N+i];
        pref[i]%=MOD;
    }
    tree=build(0, M-1);
    for(int i=0; i<M; i++) {
        //cout<<i<<'\n';
        if(A[i]) flipi(tree, i, i);
    }
    //for(ll i=0; i<N+M; i++) cout<<prd[i]<<' '<<w[i]<<'\n';
}

int count_ways(int L, int R) {
    flipi(tree, L-n, R-n);
    return saberisve();
}

Compilation message

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:99:14: warning: unused variable 'i' [-Wunused-variable]
   99 |     for(auto i:P) ch.pb(p);
      |              ^

Subtask #1
0 / 2.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Incorrect	600 KB	3rd lines differ - on the 1st token, expected: '489', found: '488'
4	Halted	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	468 KB	Output is correct
3	Incorrect	1 ms	344 KB	2nd lines differ - on the 1st token, expected: '979089518', found: '148157742'
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Incorrect	600 KB	3rd lines differ - on the 1st token, expected: '489', found: '488'
4	Halted	0 KB	-

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	500 ms	10188 KB	Output is correct
2	Correct	741 ms	19904 KB	Output is correct
3	Correct	777 ms	19904 KB	Output is correct
4	Correct	724 ms	19904 KB	Output is correct

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	500 ms	10188 KB	Output is correct
2	Correct	741 ms	19904 KB	Output is correct
3	Correct	777 ms	19904 KB	Output is correct
4	Correct	724 ms	19904 KB	Output is correct
5	Incorrect	589 ms	10076 KB	2nd lines differ - on the 1st token, expected: '904826008', found: '-95176014'
6	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	468 KB	Output is correct
3	Incorrect	1 ms	344 KB	2nd lines differ - on the 1st token, expected: '979089518', found: '148157742'
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 28.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Incorrect	600 KB	3rd lines differ - on the 1st token, expected: '489', found: '488'
4	Halted	0 KB	-

Subtask #8
0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Incorrect	600 KB	3rd lines differ - on the 1st token, expected: '489', found: '488'
4	Halted	0 KB	-