Submission #630043

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
630043	2022-08-15 14:54:26	qwerasdfzxcl	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1177 ms	24044 KiB

circuit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1'000'002'022;
vector<int> adj[100100];
int n, m, a[100100];
struct Seg1{
    ll tree[200200], sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = adj[i-sz].size();
        for (int i=sz-1;i;i--) tree[i] = tree[i<<1] * tree[i<<1|1] % MOD;
    }
    void update(int p, int x){
        for (tree[p+=sz]=x;p>1;p>>=1) tree[p>>1] = tree[p] * tree[p^1] % MOD;
    }
}tree1;
struct Seg2{
    pair<ll, ll> tree[400400];
    int lazy[400400];
    pair<ll, ll> combine(pair<ll, ll> x, pair<ll, ll> y){return {(x.first + y.first)%MOD, (x.second + y.second)%MOD};}
    void init(int i, int l, int r){
        lazy[i] = 0;
        if (l==r) {tree[i] = {0, a[l]}; return;}
        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• 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