Submission #791665

#TimeUsernameProblemLanguageResultExecution timeMemory
791665firewaterDigital Circuit (IOI22_circuit)C++17
2 / 100
652 ms20468 KiB
#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(int N, int 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; } int count_ways(int L, int 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; //}

Compilation message (stderr)

circuit.cpp: In member function 'void Tree::build(long long int, long long int, long long int)':
circuit.cpp:48:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   ll mid=l+r>>1;
      |          ~^~
circuit.cpp: In member function 'void Tree::change(long long int, long long int, long long int, long long int, long long int)':
circuit.cpp:61:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |   ll mid=L+R>>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...