Submission #1230873

#TimeUsernameProblemLanguageResultExecution timeMemory
1230873MalixDigital Circuit (IOI22_circuit)C++20
0 / 100
7 ms3276 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<ll,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) #define all(x) (x).begin(),(x).end() ll INF=1000000000000000010; int inf=1e9+10; ll M=1000002022; int n,m,k; vi a,p,lazy; vector<ll> X,Y; void update(int x,int l,int r,int u,int v){ if(u>v)return; if(lazy[x]%2){ lazy[x]=0; if(l!=r){ swap(X[2*x],Y[2*x]); swap(X[2*x+1],Y[2*x+1]); lazy[2*x]++; lazy[2*x+1]++; } } if(l==u&&r==v){ swap(X[x],Y[x]); lazy[x]++; return; } int mid=(l+r)/2; update(2*x,l,mid,u,min(v,mid)); update(2*x+1,mid+1,r,max(u,mid+1),v); X[x]=(X[2*x]+X[2*x+1])%M; Y[x]=(Y[2*x]+Y[2*x+1])%M; } void init(int N, int MM, std::vector<int> P, std::vector<int> A) { n=N;m=MM;p=P;a=A; k=n+m; X.resize(k+1,0); Y.resize(k+1,0); lazy.resize(k+1,0); vector<ll> ch(n,0); REP(i,1,k)ch[p[i]]++; REP(i,n,n+m){ vi arr(n,0); int x=i; while(x!=-1){ arr[x]=1; x=p[x]; } ll y=1; REP(j,0,n)if(!arr[j])y*=ch[j]; if(a[i-n])X[i+1]=y; else Y[i+1]=y; } for(int i=n;i>=1;i--){ X[i]=(X[2*i]+X[2*i+1])%M; Y[i]=(Y[2*i]+Y[2*i+1])%M; } return; } int count_ways(int L, int R) { update(1,0,m-1,L-n,R-n); return X[1]; }
#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...