Submission #1217408

#TimeUsernameProblemLanguageResultExecution timeMemory
1217408HappyCapybaraDigital Circuit (IOI22_circuit)C++17
46 / 100
3049 ms1564 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; #define ll long long int m = 1000002022, N, M; vector<bool> lazy; vector<pair<ll, ll>> st; void pushdown(int node){ if (!lazy[node]) return; st[node*2].first = (st[node*2].second-st[node*2].first+2*m) % m; st[node*2+1].first = (st[node*2+1].second-st[node*2+1].first+2*m) % m; lazy[node*2] = !lazy[node*2]; lazy[node*2+1] = !lazy[node*2+1]; lazy[node] = false; } void update(int l, int r, int node=1, int tl=0, int tr=M-1){ //cout << l << " " << r << " " << node << " " << tl << " " << tr << endl; if (tl != tr) pushdown(node); if (l <= tl && tr <= r){ lazy[node] = true; st[node].first = (st[node].second-st[node].first+2*m) % m; return; } int tm = (tl+tr)/2; if (l <= tm) update(l, r, node*2, tl, tm); if (tm+1 <= r) update(l, r, node*2+1, tm+1, tr); st[node].first = (st[node*2].first+st[node*2+1].first) % m; } void build(vector<ll>& tot, int node=1, int tl=0, int tr=M-1){ if (tl == tr){ st[node] = {0, tot[tl]}; return; } int tm = (tl+tr)/2; build(tot, node*2, tl, tm); build(tot, node*2+1, tm+1, tr); st[node] = {0, (st[node*2].second+st[node*2+1].second) % m}; } void init(int N, int M, vector<int> P, vector<int> A){ ::N = N; ::M = M; vector<ll> deg(N, 0); for (int i=1; i<N+M; i++) deg[P[i]]++; vector<ll> tot(M, 1); for (int i=0; i<M; i++){ vector<bool> v(N, true); int cur = i+N; while (cur != 0){ v[P[cur]] = false; cur = P[cur]; } for (int j=0; j<N; j++){ if (v[j]) tot[i] = (tot[i]*deg[j]) % m; } } st.resize(4*M); lazy.resize(4*M, false); build(tot); for (int i=0; i<M; i++){ if (A[i]) update(i, i); } } int count_ways(int L, int R){ update(L-N, R-N); return st[1].first; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...