Submission #1078496

#TimeUsernameProblemLanguageResultExecution timeMemory
1078496allin27xDigital Circuit (IOI22_circuit)C++17
100 / 100
860 ms34656 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1000002022; const int MAXN = 100007; int ar[MAXN]; int n,m; vector<int> ch[2*MAXN]; int mlt[2*MAXN]; int sgt[4*MAXN]; int rel[MAXN]; int res = 0; void update(int i, int v) { for (sgt[i+=2*MAXN]=v; i>1; i>>=1) sgt[i>>1] = (sgt[i] * sgt[i^1]) % mod; } int query(int l, int r) { int res = 1; for (l+=2*MAXN, r+=2*MAXN+1; l<r; l>>=1, r>>=1) { if (l&1) res *= sgt[l++], res %= mod; if (r&1) res *= sgt[--r], res %= mod; } return res; } int dfs0(int i) { vector<int> vl; for (int c: ch[i]) vl.push_back(dfs0(c)); if (vl.size() == 0) return 1; int ans = vl.size(); for (int i=0; i<vl.size(); i++) ans *= vl[i], ans%=mod; for (int i=0; i<vl.size(); i++) update(i, vl[i]); for (int j=0; j<vl.size(); j++) { mlt[ch[i][j]] = ((query(0, j-1)) * query(j+1, vl.size()-1)) % mod; } return ans; } void dfs1(int i, int p) { if (ch[i].size() == 0) { rel[i-n] = (p*mlt[i]) % mod; } else { for (int c: ch[i]) { dfs1(c, (p*mlt[i]) % mod); } } } int pr[MAXN]; int t[4*MAXN]; int lz[4*MAXN]; int sum(int l, int r) { if (!l) return pr[r]; int s= pr[r] - pr[l-1]; s %=mod; s+=mod; s%=mod; return s; } void push(int p, int l, int r) { if (!lz[p]) return; t[p] = sum(l,r) - t[p]; t[p] %= mod; t[p] += mod; t[p]%=mod; lz[p] = 0; if (l!=r) { lz[2*p] ^= 1; lz[2*p+1] ^= 1; } } int SumQuery(int p, int tl, int tr, int l, int r) { push(p, tl, tr); if (tl == l && tr == r) return t[p]; if (l>r) return 0; int tm = (tl+tr)/2; int a1 = SumQuery(2*p, tl, tm, l, min(tm, r)); a1 %= mod; a1+=mod; a1 %= mod; int a2 = SumQuery(2*p+1, tm+1, tr, max(tm+1, l), r); a2 %= mod; a2+=mod; a2 %= mod; return (a1 + a2) % mod; } void SumUpdate(int p, int tl, int tr, int l, int r) { push(p, tl, tr); if (tl == l && tr == r) { lz[p] = 1; push(p, tl, tr); return; } if (l>r) return; int tm = (tl+tr)/2; SumUpdate(2*p, tl, tm, l, min(tm, r)); SumUpdate(2*p+1, tm+1, tr, max(tm+1, l), r); t[p] = t[2*p] + t[2*p+1]; t[p] %= mod; } void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) { for (int i=0; i<M; i++) ar[i] = A[i]; n= N;m=M; for (int i=1; i<M+N; i++) ch[P[i]].push_back(i); for (int i=0; i<4*MAXN; i++) sgt[i] = 1; for (int i=0; i<2*MAXN; i++) mlt[i] = 1; dfs0(0); dfs1(0,1); pr[0] = rel[0]; for (int i=1; i<M; i++) pr[i] = pr[i-1] + rel[i]; for (int i=0; i<M; i++) if (A[i]) SumUpdate(1, 0, MAXN-1, i, i); } signed count_ways(signed L, signed R) { L-=n; R-=n; SumUpdate(1, 0, MAXN-1, L, R); return SumQuery(1, 0, MAXN-1, 0, m-1); }

Compilation message (stderr)

circuit.cpp: In function 'long long int dfs0(long long int)':
circuit.cpp:33:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     int ans = vl.size(); for (int i=0; i<vl.size(); i++) ans *= vl[i], ans%=mod;
      |                                        ~^~~~~~~~~~
circuit.cpp:34:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i=0; i<vl.size(); i++) update(i, vl[i]);
      |                   ~^~~~~~~~~~
circuit.cpp:35:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int j=0; j<vl.size(); j++) {
      |                   ~^~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:96:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   96 |     for (int i=0; i<M; i++) ar[i] = A[i]; n= N;m=M;
      |     ^~~
circuit.cpp:96:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   96 |     for (int i=0; i<M; i++) ar[i] = A[i]; n= N;m=M;
      |                                           ^
#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...