oj.uz

Submission #812890

# Submission time Handle Problem Language Result Execution time Memory
812890 2023-08-07T11:39:18 Z blackyuki Digital Circuit (IOI22_circuit) C++17
100 / 100
 1049 ms 23588 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;
const ll mod=1000002022;
#include "circuit.h"

struct segtree{
  ll N=1;
  vi seg,lazy,sum;
  ll f(ll a,ll b){
    return (a+b)%mod;
  }
  void init(vi a,vi b){
    while(N<a.size())N<<=1;
    seg=vi(N*2);lazy=vi(N*2);sum=vi(N*2);
    rep(i,a.size()){
      sum[i+N]=a[i];
      seg[i+N]=a[i]*b[i];
    }
    for(ll i=N-1;i>0;i--){
      sum[i]=f(sum[i*2],sum[i*2+1]);
      seg[i]=f(seg[i*2],seg[i*2+1]);
    }
  }
  void eval(ll k,ll l,ll r){
    if(!lazy[k])return;
    seg[k]=(sum[k]-seg[k])%mod;
    if(r-l>1)rep(t,2)lazy[k*2+t]^=1;
    lazy[k]=0;
  }
  ll get(){
    eval(1,0,N);
    return seg[1];
  }
  void upd(ll a,ll b,ll k=1,ll l=0,ll r=-1){
    if(r==-1)r=N;
    if(a<=l&&r<=b){
      lazy[k]^=1;eval(k,l,r);return;
    }
    if(r<=a||b<=l){
      eval(k,l,r);return;
    }
    eval(k,l,r);
    upd(a,b,k*2,l,(l+r)/2);
    upd(a,b,k*2+1,(l+r)/2,r);
    seg[k]=f(seg[k*2],seg[k*2+1]);
  }
};
segtree seg;
ll n,N_;
void init(int N, int M, std::vector<int> P, std::vector<int> A){
  N_=N;
  vvi ch(N+M);
  REP(i,1,N+M)ch[P[i]].pb(i);
  vi prod(N+M,1);
  for(ll i=N-1;i>=0;i--){
    prod[i]=ch[i].size();
    for(ll x:ch[i])prod[i]=prod[i]*prod[x]%mod;
  }
  vi dp(N+M,1);
  rep(i,N){
    vi tl(ch[i].size()+1,1),tr(ch[i].size()+1,1);
    rep(j,ch[i].size())tl[j+1]=tl[j]*prod[ch[i][j]]%mod;
    for(ll j=ch[i].size()-1;j>=0;j--)tr[j]=tr[j+1]*prod[ch[i][j]]%mod;
    rep(j,ch[i].size())dp[ch[i][j]]=dp[i]*tl[j]%mod*tr[j+1]%mod;
  }
  n=M;
  vi a(n),b(n);
  rep(i,n)a[i]=dp[N+i];
  rep(i,n)b[i]=A[i];
  seg.init(a,b);
}

int count_ways(int L, int R) {
  ll l=L-N_,r=R+1-N_;
  seg.upd(l,r);
  ll ans=seg.get();
  if(ans<0)ans+=mod;
  return ans;
}

Compilation message

circuit.cpp: In member function 'void segtree::init(vi, vi)':
circuit.cpp:32:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while(N<a.size())N<<=1;
      |           ~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 464 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 1 ms 464 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 464 KB Output is correct
21 Correct 1 ms 464 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 516 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 1 ms 464 KB Output is correct
28 Correct 1 ms 464 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 464 KB Output is correct
37 Correct 1 ms 464 KB Output is correct
38 Correct 1 ms 464 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 7212 KB Output is correct
2 Correct 743 ms 14152 KB Output is correct
3 Correct 664 ms 14152 KB Output is correct
4 Correct 685 ms 14140 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 7212 KB Output is correct
2 Correct 743 ms 14152 KB Output is correct
3 Correct 664 ms 14152 KB Output is correct
4 Correct 685 ms 14140 KB Output is correct
5 Correct 585 ms 7248 KB Output is correct
6 Correct 723 ms 14112 KB Output is correct
7 Correct 700 ms 14152 KB Output is correct
8 Correct 748 ms 14132 KB Output is correct
9 Correct 332 ms 720 KB Output is correct
10 Correct 682 ms 1104 KB Output is correct
11 Correct 757 ms 1104 KB Output is correct
12 Correct 616 ms 1104 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 467 ms 7212 KB Output is correct
14 Correct 743 ms 14152 KB Output is correct
15 Correct 664 ms 14152 KB Output is correct
16 Correct 685 ms 14140 KB Output is correct
17 Correct 585 ms 7248 KB Output is correct
18 Correct 723 ms 14112 KB Output is correct
19 Correct 700 ms 14152 KB Output is correct
20 Correct 748 ms 14132 KB Output is correct
21 Correct 332 ms 720 KB Output is correct
22 Correct 682 ms 1104 KB Output is correct
23 Correct 757 ms 1104 KB Output is correct
24 Correct 616 ms 1104 KB Output is correct
25 Correct 910 ms 22580 KB Output is correct
26 Correct 995 ms 22856 KB Output is correct
27 Correct 692 ms 22812 KB Output is correct
28 Correct 580 ms 22836 KB Output is correct
29 Correct 718 ms 22816 KB Output is correct
30 Correct 750 ms 22840 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 1 ms 464 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 464 KB Output is correct
21 Correct 1 ms 464 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 516 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 1 ms 464 KB Output is correct
28 Correct 1 ms 464 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 464 KB Output is correct
37 Correct 1 ms 464 KB Output is correct
38 Correct 1 ms 464 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Correct 463 ms 976 KB Output is correct
44 Correct 705 ms 976 KB Output is correct
45 Correct 651 ms 976 KB Output is correct
46 Correct 619 ms 1488 KB Output is correct
47 Correct 676 ms 1488 KB Output is correct
48 Correct 703 ms 1488 KB Output is correct
49 Correct 734 ms 1488 KB Output is correct
50 Correct 679 ms 1488 KB Output is correct
51 Correct 832 ms 1184 KB Output is correct
52 Correct 761 ms 1184 KB Output is correct
53 Correct 1049 ms 592 KB Output is correct
54 Correct 576 ms 1488 KB Output is correct
55 Correct 643 ms 1360 KB Output is correct
56 Correct 713 ms 1232 KB Output is correct
57 Correct 887 ms 1104 KB Output is correct
58 Correct 758 ms 1488 KB Output is correct
59 Correct 727 ms 1488 KB Output is correct
60 Correct 662 ms 1488 KB Output is correct
61 Correct 882 ms 976 KB Output is correct
62 Correct 589 ms 976 KB Output is correct
63 Correct 660 ms 976 KB Output is correct
64 Correct 732 ms 1200 KB Output is correct
65 Correct 288 ms 720 KB Output is correct
66 Correct 663 ms 1104 KB Output is correct
67 Correct 708 ms 1108 KB Output is correct
68 Correct 660 ms 1104 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 1 ms 464 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 464 KB Output is correct
21 Correct 1 ms 464 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 516 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 1 ms 464 KB Output is correct
28 Correct 1 ms 464 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 464 KB Output is correct
37 Correct 1 ms 464 KB Output is correct
38 Correct 1 ms 464 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Correct 467 ms 7212 KB Output is correct
44 Correct 743 ms 14152 KB Output is correct
45 Correct 664 ms 14152 KB Output is correct
46 Correct 685 ms 14140 KB Output is correct
47 Correct 585 ms 7248 KB Output is correct
48 Correct 723 ms 14112 KB Output is correct
49 Correct 700 ms 14152 KB Output is correct
50 Correct 748 ms 14132 KB Output is correct
51 Correct 332 ms 720 KB Output is correct
52 Correct 682 ms 1104 KB Output is correct
53 Correct 757 ms 1104 KB Output is correct
54 Correct 616 ms 1104 KB Output is correct
55 Correct 910 ms 22580 KB Output is correct
56 Correct 995 ms 22856 KB Output is correct
57 Correct 692 ms 22812 KB Output is correct
58 Correct 580 ms 22836 KB Output is correct
59 Correct 718 ms 22816 KB Output is correct
60 Correct 750 ms 22840 KB Output is correct
61 Correct 463 ms 976 KB Output is correct
62 Correct 705 ms 976 KB Output is correct
63 Correct 651 ms 976 KB Output is correct
64 Correct 619 ms 1488 KB Output is correct
65 Correct 676 ms 1488 KB Output is correct
66 Correct 703 ms 1488 KB Output is correct
67 Correct 734 ms 1488 KB Output is correct
68 Correct 679 ms 1488 KB Output is correct
69 Correct 832 ms 1184 KB Output is correct
70 Correct 761 ms 1184 KB Output is correct
71 Correct 1049 ms 592 KB Output is correct
72 Correct 576 ms 1488 KB Output is correct
73 Correct 643 ms 1360 KB Output is correct
74 Correct 713 ms 1232 KB Output is correct
75 Correct 887 ms 1104 KB Output is correct
76 Correct 758 ms 1488 KB Output is correct
77 Correct 727 ms 1488 KB Output is correct
78 Correct 662 ms 1488 KB Output is correct
79 Correct 882 ms 976 KB Output is correct
80 Correct 589 ms 976 KB Output is correct
81 Correct 660 ms 976 KB Output is correct
82 Correct 732 ms 1200 KB Output is correct
83 Correct 288 ms 720 KB Output is correct
84 Correct 663 ms 1104 KB Output is correct
85 Correct 708 ms 1108 KB Output is correct
86 Correct 660 ms 1104 KB Output is correct
87 Correct 0 ms 208 KB Output is correct
88 Correct 434 ms 21308 KB Output is correct
89 Correct 755 ms 13664 KB Output is correct
90 Correct 775 ms 13896 KB Output is correct
91 Correct 889 ms 23496 KB Output is correct
92 Correct 859 ms 23448 KB Output is correct
93 Correct 855 ms 23496 KB Output is correct
94 Correct 834 ms 23496 KB Output is correct
95 Correct 850 ms 23496 KB Output is correct
96 Correct 822 ms 15780 KB Output is correct
97 Correct 824 ms 15756 KB Output is correct
98 Correct 730 ms 8068 KB Output is correct
99 Correct 760 ms 22856 KB Output is correct
100 Correct 776 ms 19912 KB Output is correct
101 Correct 604 ms 18340 KB Output is correct
102 Correct 951 ms 16036 KB Output is correct
103 Correct 1020 ms 22812 KB Output is correct
104 Correct 749 ms 23572 KB Output is correct
105 Correct 733 ms 23588 KB Output is correct
106 Correct 783 ms 13148 KB Output is correct
107 Correct 781 ms 15612 KB Output is correct
108 Correct 806 ms 16280 KB Output is correct
109 Correct 820 ms 16188 KB Output is correct