oj.uz

답안 #722716

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722716 2023-04-12T17:26:16 Z bin9638 디지털 회로 (IOI22_circuit) C++17
0 / 100
 63 ms 37880 KB 
#include <bits/stdc++.h>
 
#ifndef SKY
#include "circuit.h"
#endif // SKY
 
using namespace std;
 
#define N 500010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back
 
int n,times;
vector<int>g[N];
ii cnt[N];
ll f[N],dp[N];
 
const ll mod=1000002022;
 
void selfmull(ll&u,ll v)
{
    v%=mod;
    u=u*v%mod;
}
 
struct IT_nhan
{
    ll ST[N*4]={};
 
    void init(int n)
    {
        for(int i=1;i<=n*4;i++)
            ST[i]=1;
    }
 
    void update(int id,int l,int r,int u,int v,ll val)
    {
        if(l>v||r<u)
            return;
      //  cout<<l<<" "<<r<<" "<<u<<" "<<v<<" "<<val<<endl;
        if(l>=u&&r<=v)
        {
            selfmull(ST[id],val);
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,u,v,val);
        update(id*2+1,mid+1,r,u,v,val);
    }
 
    ll get(int id,int l,int r,int i)
    {
        //cout<<id<<" "<<l<<" "<<r<<" "<<i<<endl;
        if(l>i||r<i)
            return 1;
        ll res=ST[id];
        if(l==r)
            return res;
        int mid=(l+r)/2;
        selfmull(res,get(id*2,l,mid,i));
        selfmull(res,get(id*2+1,mid+1,r,i));
        return res;
    }
}nhan;
 
struct IT_cong
{
    struct node
    {
        ll sum=0,val=0;
        int t=0;
    }ST[N*4];
 
    void down(int id)
    {
        if(ST[id].t==0)
            return;
        ST[id*2].t^=1;
        ST[id*2+1].t^=1;
        ST[id*2].val=(ST[id*2].sum-ST[id*2].val);
        ST[id*2+1].val=(ST[id*2+1].sum-ST[id*2+1].val);
        ST[id].t=0;
    }
 
    void update(int id,int l,int r,int i,ll val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
        //    cout<<i<<" "<<val<<endl;
            ST[id].sum=val;
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        ST[id].sum=ST[id*2].sum+ST[id*2+1].sum;
    }
 
    void flip(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return;
       // cout<<l<<" "<<r<<" "<<u<<" "<<v<<endl;
        if(l>=u&&r<=v)
        {
            ST[id].val=(ST[id].sum-ST[id].val);
            ST[id].t^=1;
            //cout<<ST[id].val<<endl;
            return;
        }
        down(id);
        int mid=(l+r)/2;
        flip(id*2,l,mid,u,v);
        flip(id*2+1,mid+1,r,u,v);
        ST[id].val=ST[id*2].val+ST[id*2+1].val;
    }
}cong;
 
void DFS(int u)
{
    f[u]=max(1,(int)g[u].size());
    cnt[u].fs=++times;
    for(auto v:g[u])
    {
        DFS(v);
        selfmull(f[u],f[v]);
    }
    cnt[u].sc=times;
    ll S=1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        nhan.update(1,1,n,cnt[v].fs,cnt[v].sc,S);
        selfmull(S,f[v]);
    }
    S=1;
    for(int i=g[u].size()-1;i>=0;i--)
    {
        int v=g[u][i];
        nhan.update(1,1,n,cnt[v].fs,cnt[v].sc,S);
        selfmull(S,f[v]);
    }
}
 
void init(int NNN, int MMM, vector<int> P, vector<int> A)
{
    n=NNN+MMM;
    for(int i=1;i<n;i++)
        g[P[i]].pb(i);
    nhan.init(n);
    DFS(0);
    for(int i=NNN;i<n;i++)
    {
        dp[i]=nhan.get(1,1,n,cnt[i].fs);
       // cout<<i<<" "<<dp[i]<<endl;
       cong.update(1,1,n,i+1,dp[i]);
    }
    for(int i=0;i<MMM;i++)
        if(A[i]==1)
            cong.flip(1,1,n,NNN+i+1,NNN+i+1);assert(0);
}
 
int count_ways(int L, int R)
{
    cong.flip(1,1,n,L+1,R+1);
    return (cong.ST[1].val%mod+mod*mod)%mod;
}
 
 
#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    vector<int>P(n+m),A(m);
    for(int i=0;i<n+m;i++)
        cin>>P[i];
    for(int i=0;i<m;i++)
        cin>>A[i];
    init(n,m,P,A);
    int q;
    cin>>q;
    while(q--)
    {
        int L,R;
        cin>>L>>R;
        cout<<count_ways(L,R)<<endl;
    }
    return 0;
}
#endif

Compilation message

circuit.cpp: In function 'void DFS(int)':
circuit.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i=0;i<g[u].size();i++)
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 24272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 24272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 24272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 63 ms 37880 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 63 ms 37880 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 24272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 24272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 24272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -