Submission #936583

#TimeUsernameProblemLanguageResultExecution timeMemory
936583GrindMachineDigital Circuit (IOI22_circuit)C++17
100 / 100
824 ms49720 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: edi (took hints from the solution to the two inputs subtask) */ const int MOD = 1000002022; const int N = 2e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "circuit.h" template<typename T> struct lazysegtree { /*=======================================================*/ struct data { array<ll,2> a; }; struct lazy { ll a; }; data d_neutral = {{0,0}}; lazy l_neutral = {0}; void merge(data &curr, data &left, data &right) { rep(j,2){ curr.a[j] = (left.a[j]+right.a[j])%MOD; } } void create(int x, int lx, int rx, T v) { tr[x].a[v.ff] = v.ss; } void modify(int x, int lx, int rx, T v) { lz[x].a = 1; } void propagate(int x, int lx, int rx) { ll v = lz[x].a; if(!v) return; swap(tr[x].a[0],tr[x].a[1]); if(rx-lx > 1){ lz[2*x+1].a ^= 1; lz[2*x+2].a ^= 1; } lz[x] = l_neutral; } /*=======================================================*/ int siz = 1; vector<data> tr; vector<lazy> lz; lazysegtree() { } lazysegtree(int n) { while (siz < n) siz *= 2; tr.assign(2 * siz, d_neutral); lz.assign(2 * siz, l_neutral); } void build(vector<T> &a, int n, int x, int lx, int rx) { if (rx - lx == 1) { if (lx < n) { create(x, lx, rx, a[lx]); } return; } int mid = (lx + rx) / 2; build(a, n, 2 * x + 1, lx, mid); build(a, n, 2 * x + 2, mid, rx); merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]); } void build(vector<T> &a, int n) { build(a, n, 0, 0, siz); } void rupd(int l, int r, T v, int x, int lx, int rx) { propagate(x, lx, rx); if (lx >= r or rx <= l) return; if (lx >= l and rx <= r) { modify(x, lx, rx, v); propagate(x, lx, rx); return; } int mid = (lx + rx) / 2; rupd(l, r, v, 2 * x + 1, lx, mid); rupd(l, r, v, 2 * x + 2, mid, rx); merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]); } void rupd(int l, int r, T v) { rupd(l, r + 1, v, 0, 0, siz); } data query(int l, int r, int x, int lx, int rx) { propagate(x, lx, rx); if (lx >= r or rx <= l) return d_neutral; if (lx >= l and rx <= r) return tr[x]; int mid = (lx + rx) / 2; data curr; data left = query(l, r, 2 * x + 1, lx, mid); data right = query(l, r, 2 * x + 2, mid, rx); merge(curr, left, right); return curr; } data query(int l, int r) { return query(l, r + 1, 0, 0, siz); } }; vector<ll> adj[N]; vector<ll> sub_ways(N); void dfs1(ll u){ sub_ways[u] = max((ll)sz(adj[u]),1ll); trav(v,adj[u]){ dfs1(v); sub_ways[u] = sub_ways[u]*sub_ways[v]%MOD; } } ll n,m; vector<int> a; vector<ll> contrib; void dfs2(ll u, ll val){ auto children = adj[u]; if(children.empty()){ contrib[u-n] = val; return; } ll siz = sz(children); children.insert(children.begin(),0); vector<ll> pref(siz+5), suff(siz+5); pref[0] = 1, suff[siz+1] = 1; rep1(i,siz){ ll v = children[i]; pref[i] = pref[i-1]*sub_ways[v]%MOD; } rev(i,siz,1){ ll v = children[i]; suff[i] = suff[i+1]*sub_ways[v]%MOD; } rep1(i,siz){ ll v = children[i]; ll new_val = val*pref[i-1]%MOD*suff[i+1]%MOD; dfs2(v,new_val); } } lazysegtree<pll> st; void init(int n_, int m_, std::vector<int> P, std::vector<int> A) { n = n_, m = m_; a = A; contrib = vector<ll>(m); rep(i,n+m){ if(P[i] != -1){ adj[P[i]].pb(i); } } dfs1(0); dfs2(0,1); vector<pll> b; rep(i,m) b.pb({a[i],contrib[i]}); st = lazysegtree<pll>(m); st.build(b,m); } int count_ways(int l, int r) { l -= n, r -= n; st.rupd(l,r,{1,1}); ll ans = st.query(0,m-1).a[1]; return ans; }
#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...