oj.uz

Submission #1070345

# Submission time Handle Problem Language Result Execution time Memory
1070345 2024-08-22T13:29:31 Z Mihailo Digital Circuit (IOI22_circuit) C++17
0 / 100
 26 ms 19516 KB 
#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];
node *tree;

ll zbir(ll l, ll r) {
    return (pref[r]-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) 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) {
    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);
}

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) {
    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++) {
        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, R);
    return saberisve();
}

Compilation message

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 19516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 19516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -