Submission #630943

#	Time	Username	Problem	Language	Result	Execution time	Memory
630943		garam1732	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1173 ms	22856 KiB

circuit

#include "circuit.h"

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
const ll MOD = 1000002022;
const int MAXN = 200200;

vector<int> adj[MAXN];
vector<ll> tree;
vector<int> lazy;
ll d[MAXN], sum[MAXN];
int in[MAXN], out[MAXN], cnt;
int x, y;

void update1(int node, int s, int e, int l, int r, int val) {
    if(l > r || e < l || r < s) return;
    if(l <= s && e <= r) {
        tree[node] = tree[node]*val%MOD;
        return;
    }

    int mid = s+e>>1;
    update1(node<<1, s, mid, l, r, val); update1(node<<1|1, mid+1, e, l, r, val);
}

ll solve1(int node, int s, int e, int idx) {
    if(e < idx || idx < s) return 1;
    ll ans = tree[node];
    if(s != e) {
        int mid = s+e>>1;
        ans = ans*solve1(node<<1, s, mid, idx)%MOD;
        ans = ans*solve1(node<<1|1, mid+1, e, idx)%MOD;
    }

    return ans;
}

void update_lazy(int node, int s, int e) {
    if(lazy[node]) {
        tree[node] = (sum[e]-sum[s-1]-tree[node]+2*MOD)%MOD;
        if(s != e) {
            lazy[node<<1] = 1-lazy[node<<1];
            lazy[node<<1|1] = 1-lazy[node<<1|1];
        }
        lazy[node] = 0;
    }
}

void update2(int node, int s, int e, int l, int r) {
    update_lazy(node, s, e);
    if(l > r || e < l || r < s) return;
    if(l <= s && e <= r) {
        tree[node] = (sum[e]-sum[s-1]-tree[node]+2*MOD)%MOD;
        if(s != e) {
            lazy[node<<1] = 1-lazy[node<<1];
            lazy[node<<1|1] = 1-lazy[node<<1|1];
        }
        return;
    }

    int mid = s+e>>1;
    update2(node<<1, s, mid, l, r); update2(node<<1|1, mid+1, e, l, r);
    tree[node] = (tree[node<<1] + tree[node<<1|1])%MOD;
}

void dfs(int here) {
    in[here] = ++cnt;
    for(int there : adj[here]) dfs(there);
    out[here] = cnt;
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    for(int i = 1; i < N+M; i++) adj[P[i]].push_back(i);

    x = N, y = M;
    dfs(0);

    int h = (int)ceil(log2(x+y));
    tree.resize(1 << (h+1), 1);

    for(int i = 0; i < N; i++) {
        update1(1, 1, cnt, 1, in[i]-1, adj[i].size());
        update1(1, 1, cnt, out[i]+1, cnt, adj[i].size());
    }

    for(int i = N; i < N+M; i++) {
        d[i] = solve1(1, 1, cnt, in[i]);
        sum[i] = (sum[i-1] + d[i])%MOD;
    }

    tree.clear();
    tree.resize(1 << (h+1));
    lazy.resize(1 << (h+1));

    for(int i = N; i < N+M; i++)
        if(A[i-N])
            update2(1, 1, x+y-1, i, i);
}

int count_ways(int L, int R) {
    update2(1, 1, x+y-1, L, R);
    update_lazy(1, 1, x+y-1);
    return tree[1];
}

Compilation message (stderr)

circuit.cpp: In function 'void update1(int, int, int, int, int, int)':
circuit.cpp:27:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |     int mid = s+e>>1;
      |               ~^~
circuit.cpp: In function 'll solve1(int, int, int, int)':
circuit.cpp:35:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid = s+e>>1;
      |                   ~^~
circuit.cpp: In function 'void update2(int, int, int, int, int)':
circuit.cpp:66:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = s+e>>1;
      |               ~^~

• 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