| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 791660 | firewater | Digital Circuit (IOI22_circuit) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "circuit.h"
#include<cstdio>
#include<vector>
#include<cstring>
//#include<cassert>
#include<iostream>
#include<algorithm>
#define ll long long
#define MX 202300
#define mod 1000002022
using namespace std;
ll n,m,a[MX],b[MX],sz[MX];
vector<ll>to[MX],pre[MX],suf[MX];
struct Tree
{
#define ls x*2
#define rs x*2+1
ll c[MX<<2],s[MX<<2],lazy[MX<<2];
void push_up(ll x)
{
c[x]=c[ls]+c[rs];
s[x]=s[ls]+s[rs];
return;
}
void get(ll x)
{
s[x]=(c[x]-s[x]+mod)%mod;
lazy[x]^=1;
return;
}
void push_down(ll x)
{
if(lazy[x]){
get(ls);
get(rs);
lazy[x]=0;
}
return;
}
void build(ll x,ll l,ll r)
{
if(l==r){
c[x]=a[l];
s[x]=a[l]*b[l];
return;
}
ll mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
push_up(x);
return;
}
void change(ll x,ll L,ll R,ll l,ll r)
{
if(L==l&&R==r){
get(x);
return;
}
push_down(x);
ll mid=L+R>>1;
if(r<=mid)change(ls,L,mid,l,r);
else if(l>mid)change(rs,mid+1,R,l,r);
else change(ls,L,mid,l,mid),change(rs,mid+1,R,mid+1,r);
push_up(x);
return;
}
}T;
void dfs(ll x)
{
sz[x]=to[x].size();
if(!sz[x])sz[x]=1;
ll sav=to[x].size();
for(ll i=0;i<sav;++i){
dfs(to[x][i]);
sz[x]=sz[x]*sz[to[x][i]]%mod;
}
return;
}
void dfs1(ll x,ll num)
{
if(x>=n)a[x-n+1]=num;
ll sav=to[x].size();
for(ll i=0;i<sav;++i){
pre[x].push_back(sz[to[x][i]]);
suf[x].push_back(sz[to[x][i]]);
}
for(ll i=1;i<sav;++i)
pre[x][i]=pre[x][i]*pre[x][i-1]%mod;
for(ll i=sav-2;i>=0;--i)
suf[x][i]=suf[x][i]*suf[x][i+1]%mod;
for(ll i=0;i<sav;++i)
dfs1(to[x][i],(i>0?pre[x][i-1]:1)*(i<sav-1?suf[x][i+1]:1)%mod*num%mod);
return;
}
void init(ll N, ll M, std::vector<int> P, std::vector<int> A) {
n=N;m=M;
for(ll i=1;i<n+m;++i)
to[P[i]].push_back(i);
for(ll i=1;i<=m;++i)
b[i]=A[i-1];
dfs(0);
dfs1(0,1);
T.build(1,1,m);
return;
}
ll count_ways(ll L, ll R) {
L=L-n+1;
R=R-n+1;
T.change(1,1,m,L,R);
return T.s[1];
}
//int main() {
// ll N, M, Q;
// assert(3 == scanf("%d %d %d", &N, &M, &Q));
// std::vector<int> P(N + M), A(M);
// for (ll i = 0; i < N + M; ++i) {
// assert(1 == scanf("%d", &P[i]));
// }
// for (ll j = 0; j < M; ++j) {
// assert(1 == scanf("%d", &A[j]));
// }
// init(N, M, P, A);
//
// for (ll i = 0; i < Q; ++i) {
// ll L, R;
// assert(2 == scanf("%d %d", &L, &R));
// printf("%d\n", count_ways(L, R));
// }
// return 0;
//}