Submission #633176

#TimeUsernameProblemLanguageResultExecution timeMemory
633176studyDigital Circuit (IOI22_circuit)C++17
2 / 100
3061 ms9172 KiB
#include <bits/stdc++.h> #include "circuit.h" using ll=long long; using namespace std; const ll mod = 1e9+2022, N = 1e5+1, M = 1e5+1; pair<ll,ll> segt[4*N+5]; bool lazy[4*N+5]; vector<int> adj[N+M]; set<int> in; int n=0, m = 0; bool ok = false; pair<ll,ll> crt; void modify(int idx, int l, int r, int L, int R){ if (r < L or l > R) return; if (l >= L and r <= R){ if (ok){ swap(segt[idx].first,segt[idx].second); lazy[idx] = 1; } else{ segt[idx] = crt; } return; } if (lazy[idx]){ lazy[2*idx] = !lazy[2*idx]; lazy[2*idx+1] = !lazy[2*idx+1]; swap(segt[2*idx].first,segt[2*idx].second); swap(segt[2*idx+1].first,segt[2*idx+1].second); lazy[idx] = 0; } int mid = (l+r)/2; modify(2*idx,l,mid,L,R); modify(2*idx+1,mid+1,r,L,R); segt[idx].first = (segt[2*idx].first+segt[2*idx+1].first)%mod; segt[idx].second = (segt[2*idx].second+segt[2*idx+1].second)%mod; } void dfs(int node){ in.emplace(node); for (int i:adj[node]){ dfs(i); } } void init(int N, int M, vector<int> P, vector<int> A){ m = M; n = N; vector<ll> deg(N+M); for (int i=1; i<N+M; ++i){ deg[P[i]]++; adj[i].emplace_back(P[i]); } for (int i=N; i<N+M; ++i){ in.clear(); dfs(i); ll prod = 1; for (int j=0; j<N; ++j){ if (!in.count(j)){ prod *= deg[j]; prod %= mod; } } if (A[i-N]){ crt = {prod,0}; } else{ crt = {0,prod}; } modify(1,0,M-1,i-N,i-N); } ok = true; } int count_ways(int L, int R){ L -= n; R -= n; modify(1,0,m-1,L,R); return segt[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...