QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#133799#4941. Tree BeautyVengeful_SpiritWA 279ms98444kbC++204.0kb2023-08-02 14:09:182023-08-02 14:09:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 14:09:22]
  • 评测
  • 测评结果:WA
  • 用时:279ms
  • 内存:98444kb
  • [2023-08-02 14:09:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int sz[N],dep[N],dfn[N],son[N],fa[N],top[N];
int n, a[N];
vector<int> e[N];
void dfs(int x,int f){
  sz[x]=1;
  dep[x]=dep[f]+1;
  for(auto v:e[x]){
    dfs(v,x);
    sz[x]+=sz[v];
    if(sz[v]>sz[son[x]])son[x]=v;
  }
}
int indec;
int dfnr[N];
void dfs2(int x,int tp){
  top[x]=tp;
  dfn[x]=++indec;
  if(son[x]){
    dfs2(son[x],tp);
  }
  for(auto v:e[x]){
    if(v!=son[x]){
      dfs2(v,v);
    }
  }
  dfnr[x]=indec;
}
long long tag[18][N<<2];
void modify(int step,int x,int l,int r,int L,int R,int v){
  if(l==L&&r==R){
    tag[step][x]+=v;
    return;
  }
  else{
    int mid=(l+r)/2;
    if(R<=mid){
      modify(step,x<<1,l,mid,L,R,v);
    }
    else if(L>mid){
      modify(step,x<<1|1,mid+1,r,L,R,v);
    } else {
      modify(step,x<<1,l,mid,L,mid,v);
      modify(step,x<<1|1,mid+1,r,mid+1,R,v);
    }
  }
}
long long query(int step,int x,int l,int r,int pos){
  if(l==r){return tag[step][x];}
  else {
    int mid=(l+r)/2;
    if(pos<=mid) return tag[step][x]+query(step,x<<1,l,mid,pos);
    else return tag[step][x]+query(step,x<<1|1,mid+1,r,pos);
  }
}
int bfn[N];
int sonl[N],sonr[N];
void bfs(){
  deque<pair<int,int>>q;
  q.push_back({1,1});
  int inded=0;
  while(!q.empty()){
    auto [x,d]=q.front();
	  bfn[x]=++inded;
	  q.pop_front();
	  for(auto v:e[x]){
	    q.push_back({v,d+1});
	  }
  }
}
void DFS(int x){
  sonl[bfn[x]]=n+1;
  sonr[bfn[x]]=-1;
  for(auto y:e[x]){
    DFS(y);
    sonl[bfn[x]]=min(sonl[bfn[x]],bfn[y]);
    sonr[bfn[x]]=max(sonr[bfn[x]],bfn[y]);
  }
}
void add(int l,int r,int num,int k){
  if(l<1||l>n||r<1||r>n) return ;
  for(int step=0;num;num/=k,++step){
    modify(step,1,1,n,l,r,num);
  }
}


// 2nd segtree
int t[N<<2],tg[N<<2];
void pushdown(int x,int l, int r){
  int mid=(r+l)/2;
  t[x<<1]+=tg[x]*(mid-l+1);t[x<<1|1]+=tg[x]*(r-mid);
  tg[x<<1]+=tg[x];tg[x<<1|1]+=tg[x];
  tg[x]=0;
}
void MODIFY(int x,int l,int r,int L,int R,int v){
  if(l==L&&r==R){
    t[x]+=v*(r-l+1);
    tg[x]+=v;
    return;
  }
  else{
    pushdown(x,l,r);
    int mid=(l+r)/2;
    if(R<=mid){
      MODIFY(x<<1,l,mid,L,R,v);
    }
    else if(L>mid){
      MODIFY(x<<1|1,mid+1,r,L,R,v);
    } else {
      MODIFY(x<<1,l,mid,L,mid,v);
      MODIFY(x<<1|1,mid+1,r,mid+1,R,v);
    }
    t[x]=t[x<<1]+t[x<<1|1];
  }
}
long long QUERY(int x,int l,int r,int L, int R){
  if(l==L&&r==R){return t[x];}
  else {
    pushdown(x,l,r);
    int mid=(l+r)/2;
    if(R<=mid) return QUERY(x<<1,l,mid,L,R);
    else if(L>mid) return QUERY(x<<1|1,mid+1,r,L,R);
    return QUERY(x<<1,l,mid,L,mid)+QUERY(x<<1|1,mid+1,r,mid+1,R);
  }
}
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  // 1 X Y K
  // 2 X
  cin >> n;
  int q;
  cin >> q;
  for(int i = 2; i <= n; ++i) {
    cin >> fa[i];
    e[fa[i]].push_back(i);
  }
  dfs(1, 0);
  dfs2(1, 1);
  bfs();
  DFS(1);
  for(int i=2;i<=n;++i)sonr[i]=max(sonr[i],sonr[i-1]);
  for(int i=n-1;i;--i)sonl[i]=min(sonl[i],sonl[i+1]);
  // for(int i=1;i<=n;++i)cerr<<i<<" "<<bfn[i]<<" "<<sonl[i]<<" "<<sonr[i]<<endl;

  for(int i = 1; i <= q; ++i) {
    int opt;
    cin >> opt;
    if(opt == 1) {
      int x, y, k;
      cin >> x >> y >> k;
      if(k==1) {
        MODIFY(1,1,n,dfn[x],dfnr[x],y);
      } else {
      int l = bfn[x], r = bfn[x];
      l = sonl[l];
      r = sonr[r];
      long long all=0;
      all=y;
      y/=k;
      while(y) {
        add(l,r,y,k);
        all+=(r-l+1)*1ll*y;
        y/=k;
        l=sonl[l];
        r=sonr[r];
        if(l>r)break;
      }
      if(x) MODIFY(1,1,n,dfn[x],dfn[x],all);
      }
    } else {
      int x;
      cin >> x;
      long long ans=QUERY(1,1,n,dfn[x],dfnr[x]);
      int l=bfn[x],r=bfn[x];
      for(int i=0;i<18;++i){
        ans+=query(i,1,1,n,bfn[x])*(r-l+1);
        l=sonl[l];
        r=sonr[r];
        if(l>r)break;
      }
      cout<<ans<<"\n";
    }
  }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 36336kb

input:

5 5
1 1 3 3
1 1 99 2
2 1
2 3
1 3 2 3
2 3

output:

245
97
99

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 4ms
memory: 19896kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 279ms
memory: 60108kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1818724600
1818724600
1818724600
672469600
2920352548
1987509504
2920352548
2782801948
2920352548
2920352548
7518672977
11295020015
7543062544
4383229800
19258702398
22947288874
15221147536
15428570536
14322314536
9119623396
12969783379
26872020588
25039643385
22398749036
27923029652
31534374661
745...

result:

ok 49891 lines

Test #4:

score: 0
Accepted
time: 252ms
memory: 97512kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
0
0
0
3263594046
72619
5712340246
12739206070
204573
14707483656
1298627484
24138783814
23788929814
30227334148
5567896640
11058006328
3665885033
24043448788
34341130004
33724575302
29212687634
38608818187
36995597194
34686046871
24686989457
13506261897
37279670571
39473230370
35944243911
70877768...

result:

ok 50054 lines

Test #5:

score: 0
Accepted
time: 270ms
memory: 57696kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
0
852481000
5140394500
5140394500
12763733400
1064250600
7675602000
10154232600
217194
12763733400
0
10688839200
5974581000
11847787800
14471583000
12763498900
7939616800
11366248900
21089515900
1354792000
20983206400
13531986400
18686842173
21417145094
21672288196
1135096000
21672288196
214001513...

result:

ok 50101 lines

Test #6:

score: 0
Accepted
time: 269ms
memory: 57284kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
0
2609835941
60408
8874354237
8874354237
992035000
4709576810
346279
17996872796
439437
5976525610
160030
424962
22313311132
518120
17873793770
9420136264
29515070242
28755008868
29253743320
31010525920
160209
370458
30408120831
17775879923
31619335669
9711754505
40004496047
39029180203
2718421907...

result:

ok 50079 lines

Test #7:

score: 0
Accepted
time: 263ms
memory: 52400kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1114953000
1114953000
870210000
0
4364660669
3871006152
3871006152
3021383652
5316836492
5356387445
5355275724
5900365152
2158922152
8789107652
2400186152
24175969012
26767485073
8838549952
539587
40002151707
48882894050
4744238283
42260305063
52556979541
323013
59142787639
327990
42567395253
599163...

result:

ok 50072 lines

Test #8:

score: 0
Accepted
time: 252ms
memory: 60256kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
0
13522878
13522878
0
13522878
2177106214
1924749597
1128089097
2129455432
34
5229518221
3470642097
8555976721
7049971097
4843730097
8129395721
8576751784
69510
17065932056
19882142649
21391663799
6835058013
16891077122
19189944244
21944719287
19053462513
20376825117
11259038508
18578260008
800651...

result:

ok 49934 lines

Test #9:

score: 0
Accepted
time: 242ms
memory: 98364kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

36008880
75795298
8472207432
11434443432
12251061129
4643385867
12515757289
326625
10914948627
11512172627
265454
7014291415
934265172
29935956747
27652996619
11012757487
40774943964
632129
52044712511
55737362888
24162966715
56477142477
43446094167
46390596500
1000924
22660809817
9407913047
6434237...

result:

ok 50168 lines

Test #10:

score: 0
Accepted
time: 248ms
memory: 56448kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1170765000
3798482000
2913904000
2393713234
130085000
3602806649
414022103
8842438664
14947788901
16803715123
24748546078
25886842078
7002353717
8548538822
28181025342
28181025344
28110597764
26300751809
25180134452
26257113717
12018504698
427129
10083788568
32041043452
25426300766
14247498993
16370...

result:

ok 49970 lines

Test #11:

score: 0
Accepted
time: 221ms
memory: 95416kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
82463388
10302298
1002
5140643388
8353247388
6046007388
2435379000
29552146089
12955436095
19194633204
46795038005
49232999049
2894773177
24047971062
47738746994
36847869803
57780761606
970436
60973175426
64592555099
36008848330
46225645413
935545
11303862792
142615
78118838856
37032566340
7719783...

result:

ok 49801 lines

Test #12:

score: 0
Accepted
time: 214ms
memory: 95836kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

133196080
133196080
133196080
133196080
0
1331488257
3354937053
1013553038
2629474127
5985463321
66962
12481351072
14867998772
3401860964
12150785402
21891294516
5399749432
25527615601
26288619030
412402
445526
26204543428
12373916783
8086123137
510138096
10635931137
19486038326
31548848582
21267426...

result:

ok 49634 lines

Test #13:

score: 0
Accepted
time: 79ms
memory: 50128kb

input:

100000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

0
0
0
0
8695956226
11186091719
11981932614
3818185104
20738340538
4220736780
16102817878
6468547176
38966274938
15466367968
46667347136
39815300485
6880661934
36907372905
52232568197
55524442921
63210406483
78314289216
113985657200
69569759400
22308422255
107294316067
83129030631
110584216911
229045...

result:

ok 50121 lines

Test #14:

score: 0
Accepted
time: 232ms
memory: 58396kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
6308651023
328942000
9383121000
9383121000
14808554000
1518012000
12463710405
25464433876
7572417858
8549661251
26748249656
936595786
13781294251
26349716656
17729462279
243532
35866816337
35866816337
22046489251
1366123786
46871339702
44024607656
661842
3306924974
46318818425
29289962650
77830216...

result:

ok 50139 lines

Test #15:

score: 0
Accepted
time: 225ms
memory: 55428kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
0
1296984000
1296984000
1344679212
1421298762
1421298762
3445506658
229938000
3586545577
3655325291
1034757080
3690130774
0
53410
7255513269
53411
13107523143
11470333844
8301305372
9349612478
12822825898
4707577508
11189999896
108855
12387887785
13743961918
19482168065
7975061253
13004949549
3923...

result:

ok 50097 lines

Test #16:

score: 0
Accepted
time: 204ms
memory: 91116kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

10544372535
9454862535
9454862535
8742445429
14363079699
26931828446
13228738397
22985085068
22439969927
15343005879
5981188038
357530
33202147348
37708347926
304486
15446260181
27861269330
28810684753
35992395967
26479817018
4091551495
54993913632
54993913632
55758161607
49637038544
9685332933
3597...

result:

ok 49988 lines

Test #17:

score: 0
Accepted
time: 196ms
memory: 79568kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

64674621
78039
78222
2206391540
1092438022
6827638128
4212159706
5503554594
4691175142
6047011799
1387230002
10542622201
9027102551
277446000
3935252977
4592200934
7807373069
14680112632
79384
171261
25076420412
36080738811
17600751788
39888494964
48327505458
47955358375
47575993741
48893155564
4575...

result:

ok 50141 lines

Test #18:

score: 0
Accepted
time: 200ms
memory: 79944kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

5418114003
507948000
5868381802
2031792000
10034298000
110373
581110000
17656140079
11549744074
5361034000
11008370039
270660
23638445294
24430887520
20741831612
8249842460
21905619126
31057578979
18512122304
22632832045
30298848924
591927
31484361691
2367482003
273257
23354157609
25325915881
257502...

result:

ok 50197 lines

Test #19:

score: 0
Accepted
time: 200ms
memory: 42900kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
2680944000
3255432000
16863990000
10704752000
3383868100
16994112021
19193968215
10342117184
5224672111
30710642782
33099429670
464811
609702
21033292330
24356214433
39472996269
35818291622
13840135214
37566363893
16206553981
19491738263
40143580200
6107255720
428863
23308663277
37694549975
427969...

result:

ok 50085 lines

Test #20:

score: 0
Accepted
time: 193ms
memory: 94632kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

5126265904
805024011
5038891269
3256699245
5965142772
6434586402
19797957307
415801
15104326285
15459995284
32091810760
23654376575
15578429900
32624627568
19348034472
25042104455
18557729791
219665
9890390120
25683379453
386530
13503926120
3597877462
11189759394
3598429701
47514696722
29905664140
2...

result:

ok 49932 lines

Test #21:

score: 0
Accepted
time: 194ms
memory: 92580kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
5867872851
3505822552
11568344851
11568344851
11568344851
2562350795
210198
9023816009
9525329193
6550325817
14361643364
14224837828
5046994095
7259310592
7611314592
14955976046
11492540134
23725287401
9171455044
26045980887
30152743287
13246312333
29628390050
27579515503
29600490873
35349600261
1...

result:

ok 49963 lines

Test #22:

score: 0
Accepted
time: 205ms
memory: 96708kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1902276812
3153022608
5858484180
158501
3385625339
8788222583
14540223877
15172532943
14914727212
8404425715
28476852835
32862090834
277980
22512570905
34163009125
39634661855
17424878747
44422793573
17424878747
12743425514
44949328037
10339847455
21656349130
19627590874
45132293014
43261888040
4326...

result:

ok 49919 lines

Test #23:

score: 0
Accepted
time: 184ms
memory: 98444kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

106935470
509909762
546340
4967830
15146
329519648
328193204
210151866
624189909
371861450
328118175
343691605
95189
7794415384
14595018392
16382749709
7985029320
188591
377765472
187220
17903265290
13065377428
1813403544
7980443126
21359694450
20586723304
25517708945
22421651353
26719718523
254513
...

result:

ok 49861 lines

Test #24:

score: 0
Accepted
time: 161ms
memory: 77280kb

input:

100000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

1276415006
608569250
1285102099
3643720335
2181494256
3554311113
1025256690
2503820073
4286234344
906253487
4618908868
1217295955
2920359075
837941980
2820652041
2239022661
4686260702
4741704087
1136867354
8598479426
2515552386
2024666204
893933836
8765925295
124286036
2159430688
8883715717
22166738...

result:

ok 49728 lines

Test #25:

score: 0
Accepted
time: 77ms
memory: 47072kb

input:

94841 97038
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

0
95178
95178
95178
4343848770
272006625
4343848770
5423741737
1975221938
5423723207
631242320
810847040
5423816793
5423798263
5423816793
9613374293
9613395857
3587400750
1308707700
9441259278
9008613083
4563293653
13794406176
14378162040
4146256808
14378051193
14225612770
18601564800
7915815388
264...

result:

ok 48409 lines

Test #26:

score: -100
Wrong Answer
time: 38ms
memory: 32456kb

input:

90709 92118
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 9138th lines differ - expected: '99300', found: '915690'