Submission #1086346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086346		underwaterkillerwhale	Digital Circuit (IOI22_circuit)	C++17	100 / 100	862 ms	40948 KiB

circuit

//#include "circuit.h"

#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 2022;
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 350;

int n, m, Q;
int P[N], a[N];
vector<int> ke[N];
pii qr[N];


bool sub4c = 0, sub5c;

namespace sub3 {
    const int N1 = 2e3 + 7;
    ll dp[N1][2], f[N1][N1];

    void dfs (int u, int p) {
        iter (&v, ke[u]) {
            if (v != p) {///aware!!!!!!!!
                dfs(v, u);
            }
        }
        int m = SZ(ke[u]);
        rep (i, 0, m)
        rep (j, 0, m) f[i][j] = 0;
        f[0][0] = 1;
        rep (i, 1, m) {
            int v = ke[u][i - 1];
            rep (j, 0, m ) {
                f[i][j] = f[i - 1][j] * dp[v][0] % Mod;
                if (j) (f[i][j] += f[i - 1][j - 1] * dp[v][1] % Mod) %= Mod;
            }
        }
        ll pre = f[m][0];
        rep (i, 1, m) {
            (dp[u][0] += pre) %= Mod;
            (pre += f[m][i]) %= Mod;
        }
        ll suf = 0;
        reb (i, m, 1) {
            (suf += f[m][i]) %= Mod;
            (dp[u][1] += suf) %= Mod;
        }
//        cout << u<<" "<<dp[u][0]<<","<<dp[u][1] <<"\n";
    }

    ll solution(int L, int R) {
        rep (i, L, R) a[i] ^= 1;
        rep (i, 1, n + m) rep (j, 0, 1) dp[i][j] = 0;
        rep (i, n + 1, n + m) dp[i][a[i]] = 1;
        dfs(1, 0);
        return dp[1][1];
    }
}

namespace sub4 {
    ll dp[N][2];
    int pa[N];

    bool check () {
        int K = 1; while (K < m) K *= 2;
        if (K == m && m == n + 1) {
            rep (i, 1, n + m - 1) if (P[i + 1] != (i - 1) / 2) return 0;
            return 1;
        }
        return 0;
    }

    void update (int u) {
        if (SZ(ke[u]) == 0) {
            dp[u][a[u]] = 1;
            dp[u][a[u] ^ 1] = 0;
            return;
        }
        int v1 = ke[u][0], v2 = ke[u][1];
        ll delta = (dp[v1][0] * dp[v2][1] % Mod + dp[v1][1] * dp[v2][0] % Mod) % Mod;
        dp[u][0] = (delta + 2LL * dp[v1][0] * dp[v2][0] % Mod) % Mod;
        dp[u][1] = (delta + 2LL * dp[v1][1] * dp[v2][1] % Mod) % Mod;
    }

    void dfs (int u, int p) {
        pa[u] = p;
        iter (&v, ke[u]) {
            dfs(v, u);
        }
        update (u);
    }

    void init () {
        dfs(1, 0);
    }

    int solution(int u) {
        while (u != 0) {
            update(u);
            u = pa[u];
        }
        return dp[1][1];
    }
}

namespace sub6 {

    struct Segment_Tree_0 {
        int m;
        ll lz[N << 2];

        void init (int n ) {
            m = n;
            rep (i, 1, n << 2) lz[i] = 1;
        }

        void down (int id) {
            rep (i, id << 1, id << 1 | 1) {
                (lz[i] *= lz[id]) %= Mod;
            }
            lz[id] = 1;
        }

        void update (int id, int l, int r, int u, int v, ll val) {
            if (l > v || r < u) return;
            if (l >= u && r <= v){
                (lz[id] *= val) %= Mod;
                return;
            }
            int mid = l + r >> 1;
            down(id);
            update (id << 1, l, mid, u, v, val);
            update (id << 1 | 1, mid + 1, r, u, v, val);
        }

        ll get (int id, int l, int r, int pos) {
            if (l > pos || r < pos) return -1;
            if (l == r) return lz[id];
            down(id);
            int mid = l + r >> 1;
            return max (get (id << 1, l, mid, pos),
                        get (id << 1 | 1, mid + 1, r, pos));
        }

        void update (int u, int v, ll val) {
            update (1, 1, m, u, v, val);
        }
        ll get (int pos) {
            return get (1, 1, m, pos);
        }
    }ST0;

    int ein[N], eout[N], szC[N];
    ll pre[N], suf[N], tot[N];

    struct Segment_Tree_1 {
        int m;
        ll st[N << 2][2];
        bool lz[N << 2];

        void build (int id, int l, int r) {
            if (l == r) {
                ll curV = ST0.get(ein[l + n]);
//                cout << l + n <<" "<<curV<<"\n";
                st[id][a[l + n]] = curV;
                return;
            }
            int mid = l + r >> 1;
            build (id << 1, l, mid);
            build (id << 1 | 1, mid + 1, r);
            rep (i, 0, 1) st[id][i] = (st[id << 1][i] + st[id << 1 | 1][i]) % Mod;
        }

        void down (int id) {
            if (lz[id]) {
                rep (i, id << 1, id << 1 | 1) {
                    swap(st[i][0], st[i][1]);
                    lz[i] ^= 1;
                }
                lz[id] = 0;
            }
        }

        void flip (int id, int l, int r, int u, int v) {
            if (l > v || r < u) return;
            if (l >= u && r <= v) {
                swap(st[id][0], st[id][1]);
                lz[id] ^= 1;
                return;
            }
            int mid = l + r >> 1;
            down(id);
            flip (id << 1, l, mid, u, v);
            flip (id << 1 | 1, mid + 1, r, u, v);
            rep (i, 0, 1) st[id][i] = (st[id << 1][i] + st[id << 1 | 1][i]) % Mod;
        }

        void init (int n) {
            m = n;
            build(1, 1, m);
        }

        void flip (int u, int v) {
            flip (1, 1, m, u, v);
        }

    }ST1;

    void pdfs (int u) {
        static int time_dfs = 0;
        szC[u] = 1;
        ein[u] = ++time_dfs;
        iter (&v, ke[u]) {
            pdfs(v);
            szC[u] += szC[v];
        }
        eout[u] = time_dfs;

        int K = SZ(ke[u]);
        tot[u] = max(1, K);
        iter (&v, ke[u]) tot[u] = tot[u] * tot[v] % Mod;
        pre[0] = 1;
        rep (i, 1, K) pre[i] = pre[i - 1] * tot[ke[u][i - 1]] % Mod;
        suf[K + 1] = 1;
        reb (i, K, 1) suf[i] = suf[i + 1] * tot[ke[u][i - 1]] % Mod;
        rep (i, 1, K) {
            int v = ke[u][i - 1];
            ST0.update (ein[v], eout[v], pre[i - 1] * suf[i + 1] % Mod);
        }
    }
    ///offset ed
    void init () {
        ST0.init(n + m);
        pdfs(1);
        ST1.init(m);
    }

    int solution (int L, int R) {
        L -= n;
        R -= n;
        ST1.flip(L, R);
        return ST1.st[1][1];
    }

}

int count_ways (int L, int R) { ///int function must have a return value
    ++L,++R;
//    if (n <= 1000 & m <= 1000)
//        return sub3 :: solution(L, R);
//    else
        return sub6 :: solution(L, R);
}

void init (int _n, int _m, vector<int> _P, vector<int> _a) {
    n = _n;
    m = _m;
    rep (i, 1, n + m) P[i] = _P[i - 1];
    rep (i, 1, m) a[i + n] = _a[i - 1];
    rep (i, 1, n + m) {
        if (i > 1) ke[P[i] + 1].pb(i);
    }
    sub4c = sub4 :: check();
    if (sub4c) sub4 :: init();
    sub6 :: init();
}

void solution() {
    cin >> n >> m >> Q;
    rep (i, 1, n + m) {
        cin >> P[i];
        if (i > 1) ke[P[i] + 1].pb(i);
    }
    rep (i, n + 1, n + m) cin >> a[i];
    sub4c = sub4 :: check();
    if (sub4c) sub4 :: init();
    sub6 :: init();
    rep (i, 1, Q) {
        int L, R;
        cin >> L >> R;
        cout << count_ways(L, R) <<"\n";
    }
}

//#define file(name) freopen(name".inp","r",stdin); \
//freopen(name".out","w",stdout);
//int main () {
////    file("c");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    init(3, 4, {-1, 0, 1, 2, 1, 1, 0}, {1, 0, 1, 0});
////    cout << count_ways(3, 4) <<"\n";
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
no bug +5
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6

*/

Compilation message (stderr)

circuit.cpp:305:1: warning: multi-line comment [-Wcomment]
  305 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^
circuit.cpp: In member function 'void sub6::Segment_Tree_0::update(int, int, int, int, int, long long int)':
circuit.cpp:150:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |             int mid = l + r >> 1;
      |                       ~~^~~
circuit.cpp: In member function 'long long int sub6::Segment_Tree_0::get(int, int, int, int)':
circuit.cpp:160:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |             int mid = l + r >> 1;
      |                       ~~^~~
circuit.cpp: In member function 'void sub6::Segment_Tree_1::build(int, int, int)':
circuit.cpp:188:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  188 |             int mid = l + r >> 1;
      |                       ~~^~~
circuit.cpp: In member function 'void sub6::Segment_Tree_1::flip(int, int, int, int, int)':
circuit.cpp:211:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  211 |             int mid = l + r >> 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