Submission #1085951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085951		modwwe	Digital Circuit (IOI22_circuit)	C++17	100 / 100	774 ms	22580 KiB

circuit

#include "circuit.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int2 long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9')
    {
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}

void phongbeo();
const int inf=1e9;
const int mod2=1e9 + 2022;
const int  mod1=998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;

};

int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid,l2,r2,center;
int  i,s10,s12;
int kk;
int el=29;

vector<int> v[200001];
int2 dp[200001];
bool a[100001];
int2 dp2[200001];
int2 le[200001];
int2 ri[200001];
void dfs(int x)
{
    if(v[x].size()==0)dp[x]=1;
    else dp[x]=v[x].size();
    for(auto f:v[x])
    {
        dfs(f);
        dp[x]=dp[x]*dp[f]%mod2;
    }
}
void dfs2(int x)
{
    le[0]=1;
    if(x==1)dp2[x]=1;
    for(int i=0; i<v[x].size(); i++)
    {
        le[i+1]=le[i]*dp[v[x][i]]%mod2;
        dp2[v[x][i]]=dp2[x];
    }
    ri[v[x].size()+1]=1;
    for(int i=v[x].size()-1; i>=0; --i)
        ri[i+1]=ri[i+2]*dp[v[x][i]]%mod2;
    for(int i=0; i<v[x].size(); i++)
    { ///if(x==1) cout<<v[x][i],debug
        dp2[v[x][i]]=le[i]*ri[i+2]%mod2;
                dp2[v[x][i]]=dp2[v[x][i]]*dp2[x]%mod2;

    }
    for(auto f:v[x])
        dfs2(f);
}
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0) x+=mod2;
    return x+y;
}
struct IT
{
    int t[400001];
    int t2[400001];
    int t3[400001];
    void build(int node,int l,int r)
    {
        if(l==r)
        {
            if(a[l]==1)
                t[node]=dp2[l+n]%mod2;
            t2[node]=dp2[l+n];
            return;
        }
        int mid=l+r>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        t[node]=add(t[node<<1],t[node<<1|1]);
        t2[node]=add(t2[node<<1],t2[node<<1|1]);
    }
    void ff(int x)
    {
        for(int i=x*2; i<=x*2+1; i++)
        {
            t3[i]=1-t3[i];
            t[i]=add(-t[i],t2[i]);
        }
        t3[x]=0;
    }
    void upd(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
            t3[node]=1-t3[node];
            t[node]=add(-t[node],t2[node]);
            return;
        }
        if(t3[node]!=0) ff(node);
        int mid=l+r>>1;
        upd(node<<1,l,mid,l1,r1);
        upd(node<<1|1,mid+1,r,l1,r1);
        t[node]=add(t[node<<1],t[node<<1|1]);
    }
} st;
int count_ways(int l, int r) {

        st.upd(1,1,m,l-n+1,r-n+1);
        return st.t[1];
}
void init(int N, int M, vector<int> P, vector<int> A)
{

    n=N;
    m=M;
    for(int i=1; i<=n+m; i++)
    {
        l=P[i-1];
        if(i>1)
        {
            v[l+1].pb(i);
        }
    }
    for(int i=1; i<=m; i++)
        a[i]=A[i-1];
    dp2[0]=1;
    dfs(1);
    dfs2(1);
    st.build(1,1,m);
}

/**
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6
*/

Compilation message (stderr)

circuit.cpp: In function 'void dfs2(int)':
circuit.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=0; i<v[x].size(); i++)
      |                  ~^~~~~~~~~~~~
circuit.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=0; i<v[x].size(); i++)
      |                  ~^~~~~~~~~~~~
circuit.cpp: In member function 'void IT::build(int, int, int)':
circuit.cpp:126:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |         int mid=l+r>>1;
      |                 ~^~
circuit.cpp: In member function 'void IT::upd(int, int, int, int, int)':
circuit.cpp:151:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  151 |         int mid=l+r>>1;
      |                 ~^~

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11