oj.uz

답안 #626529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
626529 2022-08-11T14:01:05 Z haojiandan 송신탑 (IOI22_towers) C++17
100 / 100
 1223 ms 44900 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+10;
const int maxm=maxn*40;
const int INF=2e9;
int n,h[maxn],tot,st[maxn];
int mx[maxn*4],ls[maxm],rs[maxm],tr[maxm];
void build(int l,int r,int root) {
	if (l==r) { mx[root]=h[l]; return; }
	int mid=(l+r)>>1;
	build(l,mid,root<<1),build(mid+1,r,root<<1|1);
	mx[root]=max(mx[root<<1],mx[root<<1|1]);
}
int querymx(int L,int R,int l,int r,int root) {
	if (L>R) return -INF;
	if (L<=l&&r<=R) return mx[root];
	int mid=(l+r)>>1,res=0;
	if (L<=mid) res=querymx(L,R,l,mid,root<<1);
	if (mid<R) res=max(res,querymx(L,R,mid+1,r,root<<1|1));
	return res;
}
int L[maxn],R[maxn],rt[maxn];
namespace Seg {
	int mxR[maxn*4],mxL[maxn*4];
	void build(int l,int r,int root) {
		if (l==r) { mxR[root]=R[l],mxL[root]=L[l]; return; }
		int mid=(l+r)>>1;
		build(l,mid,root<<1),build(mid+1,r,root<<1|1);
		mxR[root]=max(mxR[root<<1],mxR[root<<1|1]);
		mxL[root]=max(mxL[root<<1],mxL[root<<1|1]);
	}
	int query1(int L,int R,int l,int r,int root,int delta) {
		if (mxR[root]<delta) return n+1;
		if (L<=l&&r<=R) {
			if (l==r) return l;
			int mid=(l+r)>>1;
			if (mxR[root<<1]>=delta) return query1(L,R,l,mid,root<<1,delta);
			return query1(L,R,mid+1,r,root<<1|1,delta);
		}
		int mid=(l+r)>>1,res=n+1;
		if (L<=mid) { res=query1(L,R,l,mid,root<<1,delta); if (res<=n) return res; }
		if (mid<R) res=query1(L,R,mid+1,r,root<<1|1,delta); return res;
	}
	int query2(int L,int R,int l,int r,int root,int delta) {
		if (mxL[root]<delta) return 0;
		if (L<=l&&r<=R) {
			if (l==r) return l;
			int mid=(l+r)>>1;
			if (mxL[root<<1|1]>=delta) return query2(L,R,mid+1,r,root<<1|1,delta);
			return query2(L,R,l,mid,root<<1,delta);
		}
		int mid=(l+r)>>1,res=0;
		if (mid<R) { res=query2(L,R,mid+1,r,root<<1|1,delta); if (res) return res; }
		if (L<=mid) res=query2(L,R,l,mid,root<<1,delta); return res;
	}
};
void add(int x,int l,int r,int &root) {
	tot++; ls[tot]=ls[root],rs[tot]=rs[root],tr[tot]=tr[root]+1; root=tot;
	if (l==r) return;
	int mid=((ll)l+r)>>1;
	if (x<=mid) add(x,l,mid,ls[root]); else add(x,mid+1,r,rs[root]);
}
int query(int L,int R,int l,int r,int x,int y) {
	if (L<=l&&r<=R) return tr[y]-tr[x];
	int res=0,mid=((ll)l+r)>>1;
	if (L<=mid) res+=query(L,R,l,mid,ls[x],ls[y]);
	if (mid<R) res+=query(L,R,mid+1,r,rs[x],rs[y]);
	return res;
}
void init(int _n, vector<int> H) {
	n=_n;
	for (int i=1;i<=n;i++) h[i]=H[i-1];
	build(1,n,1);
	for (int i=1;i<=n;i++) {
		while (tot&&h[st[tot]]>h[i]) tot--;
		if (!tot) L[i]=INF; else {
			L[i]=querymx(st[tot]+1,i-1,1,n,1);
			if (L[i]>=0) L[i]-=h[i];
		}
		st[++tot]=i;
	}
	tot=0;
	for (int i=n;i>=1;i--) {
		while (tot&&h[st[tot]]>h[i]) tot--;
		if (!tot) R[i]=INF; else {
			R[i]=querymx(i+1,st[tot]-1,1,n,1);
			if (R[i]>=0) R[i]-=h[i];
		}
		st[++tot]=i;
	}
	Seg::build(1,n,1);
	for (int i=1;i<=n;i++) rt[i]=rt[i-1],add(min(L[i],R[i]),-INF,INF,rt[i]);
}
int max_towers(int l, int r, int D) {
	l++,r++;
	l=Seg::query1(l,n,1,n,1,D);
	r=Seg::query2(1,r,1,n,1,D);
	if (l>r) return 1;
	//printf("%d %d\n",l,r);
	return 2+(l+1<=r-1?query(D,INF,-INF,INF,rt[l],rt[r-1]):-1);
}

Compilation message

towers.cpp: In function 'int Seg::query1(int, int, int, int, int, int)':
towers.cpp:44:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |   if (mid<R) res=query1(L,R,mid+1,r,root<<1|1,delta); return res;
      |   ^~
towers.cpp:44:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |   if (mid<R) res=query1(L,R,mid+1,r,root<<1|1,delta); return res;
      |                                                       ^~~~~~
towers.cpp: In function 'int Seg::query2(int, int, int, int, int, int)':
towers.cpp:56:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   56 |   if (L<=mid) res=query2(L,R,l,mid,root<<1,delta); return res;
      |   ^~
towers.cpp:56:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   56 |   if (L<=mid) res=query2(L,R,l,mid,root<<1,delta); return res;
      |                                                    ^~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 423 ms 26520 KB Output is correct
2 Correct 736 ms 44872 KB Output is correct
3 Correct 930 ms 44840 KB Output is correct
4 Correct 944 ms 44884 KB Output is correct
5 Correct 879 ms 44900 KB Output is correct
6 Correct 766 ms 44856 KB Output is correct
7 Correct 822 ms 44888 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 1232 KB Output is correct
10 Correct 1 ms 1232 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 1232 KB Output is correct
3 Correct 1 ms 1232 KB Output is correct
4 Correct 1 ms 1232 KB Output is correct
5 Correct 1 ms 1232 KB Output is correct
6 Correct 2 ms 1232 KB Output is correct
7 Correct 1 ms 1232 KB Output is correct
8 Correct 1 ms 1232 KB Output is correct
9 Correct 1 ms 1232 KB Output is correct
10 Correct 1 ms 1232 KB Output is correct
11 Correct 2 ms 1356 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 2 ms 1232 KB Output is correct
14 Correct 1 ms 1232 KB Output is correct
15 Correct 1 ms 1232 KB Output is correct
16 Correct 2 ms 1232 KB Output is correct
17 Correct 3 ms 1232 KB Output is correct
18 Correct 1 ms 1232 KB Output is correct
19 Correct 2 ms 1232 KB Output is correct
20 Correct 1 ms 1232 KB Output is correct
21 Correct 2 ms 1232 KB Output is correct
22 Correct 2 ms 1232 KB Output is correct
23 Correct 1 ms 1280 KB Output is correct
24 Correct 1 ms 1232 KB Output is correct
25 Correct 1 ms 720 KB Output is correct
26 Correct 1 ms 1232 KB Output is correct
27 Correct 2 ms 1232 KB Output is correct
28 Correct 1 ms 1232 KB Output is correct
29 Correct 1 ms 1232 KB Output is correct
30 Correct 2 ms 1232 KB Output is correct
31 Correct 2 ms 1232 KB Output is correct
32 Correct 1 ms 1232 KB Output is correct
33 Correct 1 ms 1232 KB Output is correct
34 Correct 1 ms 1232 KB Output is correct
35 Correct 2 ms 1232 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 1232 KB Output is correct
3 Correct 1 ms 1232 KB Output is correct
4 Correct 1 ms 1232 KB Output is correct
5 Correct 1 ms 1232 KB Output is correct
6 Correct 2 ms 1232 KB Output is correct
7 Correct 1 ms 1232 KB Output is correct
8 Correct 1 ms 1232 KB Output is correct
9 Correct 1 ms 1232 KB Output is correct
10 Correct 1 ms 1232 KB Output is correct
11 Correct 2 ms 1356 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 2 ms 1232 KB Output is correct
14 Correct 1 ms 1232 KB Output is correct
15 Correct 1 ms 1232 KB Output is correct
16 Correct 2 ms 1232 KB Output is correct
17 Correct 3 ms 1232 KB Output is correct
18 Correct 1 ms 1232 KB Output is correct
19 Correct 2 ms 1232 KB Output is correct
20 Correct 1 ms 1232 KB Output is correct
21 Correct 2 ms 1232 KB Output is correct
22 Correct 2 ms 1232 KB Output is correct
23 Correct 1 ms 1280 KB Output is correct
24 Correct 1 ms 1232 KB Output is correct
25 Correct 1 ms 720 KB Output is correct
26 Correct 1 ms 1232 KB Output is correct
27 Correct 2 ms 1232 KB Output is correct
28 Correct 1 ms 1232 KB Output is correct
29 Correct 1 ms 1232 KB Output is correct
30 Correct 2 ms 1232 KB Output is correct
31 Correct 2 ms 1232 KB Output is correct
32 Correct 1 ms 1232 KB Output is correct
33 Correct 1 ms 1232 KB Output is correct
34 Correct 1 ms 1232 KB Output is correct
35 Correct 2 ms 1232 KB Output is correct
36 Correct 41 ms 28580 KB Output is correct
37 Correct 71 ms 44396 KB Output is correct
38 Correct 64 ms 44460 KB Output is correct
39 Correct 65 ms 44428 KB Output is correct
40 Correct 69 ms 44440 KB Output is correct
41 Correct 65 ms 44456 KB Output is correct
42 Correct 64 ms 44352 KB Output is correct
43 Correct 44 ms 44836 KB Output is correct
44 Correct 56 ms 44796 KB Output is correct
45 Correct 56 ms 44712 KB Output is correct
46 Correct 48 ms 44660 KB Output is correct
47 Correct 61 ms 44444 KB Output is correct
48 Correct 64 ms 44552 KB Output is correct
49 Correct 79 ms 44456 KB Output is correct
50 Correct 44 ms 44872 KB Output is correct
51 Correct 43 ms 44836 KB Output is correct
52 Correct 65 ms 44464 KB Output is correct
53 Correct 79 ms 44340 KB Output is correct
54 Correct 65 ms 44452 KB Output is correct
55 Correct 42 ms 44852 KB Output is correct
56 Correct 55 ms 44616 KB Output is correct
57 Correct 64 ms 43052 KB Output is correct
58 Correct 70 ms 44408 KB Output is correct
59 Correct 62 ms 44472 KB Output is correct
60 Correct 67 ms 44440 KB Output is correct
61 Correct 68 ms 44528 KB Output is correct
62 Correct 68 ms 44384 KB Output is correct
63 Correct 65 ms 44440 KB Output is correct
64 Correct 51 ms 44816 KB Output is correct
65 Correct 42 ms 44872 KB Output is correct
66 Correct 53 ms 44748 KB Output is correct
67 Correct 48 ms 44852 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 773 ms 44196 KB Output is correct
2 Correct 1020 ms 44512 KB Output is correct
3 Correct 933 ms 44384 KB Output is correct
4 Correct 883 ms 44440 KB Output is correct
5 Correct 905 ms 44440 KB Output is correct
6 Correct 740 ms 44452 KB Output is correct
7 Correct 951 ms 44344 KB Output is correct
8 Correct 909 ms 44856 KB Output is correct
9 Correct 901 ms 44896 KB Output is correct
10 Correct 981 ms 44728 KB Output is correct
11 Correct 904 ms 44716 KB Output is correct
12 Correct 920 ms 44812 KB Output is correct
13 Correct 877 ms 44840 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 2 ms 1232 KB Output is correct
16 Correct 1 ms 1232 KB Output is correct
17 Correct 63 ms 44476 KB Output is correct
18 Correct 69 ms 44388 KB Output is correct
19 Correct 66 ms 44432 KB Output is correct
20 Correct 44 ms 44872 KB Output is correct
21 Correct 50 ms 44872 KB Output is correct
22 Correct 63 ms 44464 KB Output is correct
23 Correct 72 ms 44364 KB Output is correct
24 Correct 67 ms 44448 KB Output is correct
25 Correct 42 ms 44832 KB Output is correct
26 Correct 53 ms 44600 KB Output is correct
27 Correct 2 ms 1232 KB Output is correct
28 Correct 2 ms 1232 KB Output is correct
29 Correct 2 ms 1232 KB Output is correct
30 Correct 1 ms 1232 KB Output is correct
31 Correct 1 ms 1232 KB Output is correct
32 Correct 1 ms 1232 KB Output is correct
33 Correct 2 ms 1232 KB Output is correct
34 Correct 1 ms 1232 KB Output is correct
35 Correct 2 ms 1160 KB Output is correct
36 Correct 1 ms 1232 KB Output is correct

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 10828 KB Output is correct
2 Correct 846 ms 44380 KB Output is correct
3 Correct 986 ms 44476 KB Output is correct
4 Correct 919 ms 44360 KB Output is correct
5 Correct 979 ms 44356 KB Output is correct
6 Correct 830 ms 44444 KB Output is correct
7 Correct 985 ms 44360 KB Output is correct
8 Correct 926 ms 44860 KB Output is correct
9 Correct 727 ms 44832 KB Output is correct
10 Correct 917 ms 44688 KB Output is correct
11 Correct 840 ms 44716 KB Output is correct
12 Correct 63 ms 44364 KB Output is correct
13 Correct 65 ms 44384 KB Output is correct
14 Correct 65 ms 44360 KB Output is correct
15 Correct 42 ms 44848 KB Output is correct
16 Correct 55 ms 44588 KB Output is correct
17 Correct 80 ms 43032 KB Output is correct
18 Correct 65 ms 44364 KB Output is correct
19 Correct 65 ms 44452 KB Output is correct
20 Correct 65 ms 44468 KB Output is correct
21 Correct 69 ms 44460 KB Output is correct
22 Correct 73 ms 44376 KB Output is correct
23 Correct 67 ms 44464 KB Output is correct
24 Correct 43 ms 44884 KB Output is correct
25 Correct 41 ms 44900 KB Output is correct
26 Correct 70 ms 44632 KB Output is correct
27 Correct 45 ms 44844 KB Output is correct
28 Correct 1 ms 1232 KB Output is correct
29 Correct 2 ms 1232 KB Output is correct
30 Correct 2 ms 1232 KB Output is correct
31 Correct 1 ms 1232 KB Output is correct
32 Correct 1 ms 1232 KB Output is correct
33 Correct 1 ms 720 KB Output is correct
34 Correct 2 ms 1232 KB Output is correct
35 Correct 2 ms 1232 KB Output is correct
36 Correct 2 ms 1232 KB Output is correct
37 Correct 2 ms 1232 KB Output is correct
38 Correct 2 ms 1232 KB Output is correct
39 Correct 1 ms 1232 KB Output is correct
40 Correct 1 ms 1232 KB Output is correct
41 Correct 1 ms 1232 KB Output is correct
42 Correct 1 ms 1232 KB Output is correct
43 Correct 1 ms 1232 KB Output is correct

Subtask #6
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 1232 KB Output is correct
3 Correct 1 ms 1232 KB Output is correct
4 Correct 1 ms 1232 KB Output is correct
5 Correct 1 ms 1232 KB Output is correct
6 Correct 2 ms 1232 KB Output is correct
7 Correct 1 ms 1232 KB Output is correct
8 Correct 1 ms 1232 KB Output is correct
9 Correct 1 ms 1232 KB Output is correct
10 Correct 1 ms 1232 KB Output is correct
11 Correct 2 ms 1356 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 2 ms 1232 KB Output is correct
14 Correct 1 ms 1232 KB Output is correct
15 Correct 1 ms 1232 KB Output is correct
16 Correct 2 ms 1232 KB Output is correct
17 Correct 3 ms 1232 KB Output is correct
18 Correct 1 ms 1232 KB Output is correct
19 Correct 2 ms 1232 KB Output is correct
20 Correct 1 ms 1232 KB Output is correct
21 Correct 2 ms 1232 KB Output is correct
22 Correct 2 ms 1232 KB Output is correct
23 Correct 1 ms 1280 KB Output is correct
24 Correct 1 ms 1232 KB Output is correct
25 Correct 1 ms 720 KB Output is correct
26 Correct 1 ms 1232 KB Output is correct
27 Correct 2 ms 1232 KB Output is correct
28 Correct 1 ms 1232 KB Output is correct
29 Correct 1 ms 1232 KB Output is correct
30 Correct 2 ms 1232 KB Output is correct
31 Correct 2 ms 1232 KB Output is correct
32 Correct 1 ms 1232 KB Output is correct
33 Correct 1 ms 1232 KB Output is correct
34 Correct 1 ms 1232 KB Output is correct
35 Correct 2 ms 1232 KB Output is correct
36 Correct 41 ms 28580 KB Output is correct
37 Correct 71 ms 44396 KB Output is correct
38 Correct 64 ms 44460 KB Output is correct
39 Correct 65 ms 44428 KB Output is correct
40 Correct 69 ms 44440 KB Output is correct
41 Correct 65 ms 44456 KB Output is correct
42 Correct 64 ms 44352 KB Output is correct
43 Correct 44 ms 44836 KB Output is correct
44 Correct 56 ms 44796 KB Output is correct
45 Correct 56 ms 44712 KB Output is correct
46 Correct 48 ms 44660 KB Output is correct
47 Correct 61 ms 44444 KB Output is correct
48 Correct 64 ms 44552 KB Output is correct
49 Correct 79 ms 44456 KB Output is correct
50 Correct 44 ms 44872 KB Output is correct
51 Correct 43 ms 44836 KB Output is correct
52 Correct 65 ms 44464 KB Output is correct
53 Correct 79 ms 44340 KB Output is correct
54 Correct 65 ms 44452 KB Output is correct
55 Correct 42 ms 44852 KB Output is correct
56 Correct 55 ms 44616 KB Output is correct
57 Correct 64 ms 43052 KB Output is correct
58 Correct 70 ms 44408 KB Output is correct
59 Correct 62 ms 44472 KB Output is correct
60 Correct 67 ms 44440 KB Output is correct
61 Correct 68 ms 44528 KB Output is correct
62 Correct 68 ms 44384 KB Output is correct
63 Correct 65 ms 44440 KB Output is correct
64 Correct 51 ms 44816 KB Output is correct
65 Correct 42 ms 44872 KB Output is correct
66 Correct 53 ms 44748 KB Output is correct
67 Correct 48 ms 44852 KB Output is correct
68 Correct 773 ms 44196 KB Output is correct
69 Correct 1020 ms 44512 KB Output is correct
70 Correct 933 ms 44384 KB Output is correct
71 Correct 883 ms 44440 KB Output is correct
72 Correct 905 ms 44440 KB Output is correct
73 Correct 740 ms 44452 KB Output is correct
74 Correct 951 ms 44344 KB Output is correct
75 Correct 909 ms 44856 KB Output is correct
76 Correct 901 ms 44896 KB Output is correct
77 Correct 981 ms 44728 KB Output is correct
78 Correct 904 ms 44716 KB Output is correct
79 Correct 920 ms 44812 KB Output is correct
80 Correct 877 ms 44840 KB Output is correct
81 Correct 0 ms 336 KB Output is correct
82 Correct 2 ms 1232 KB Output is correct
83 Correct 1 ms 1232 KB Output is correct
84 Correct 63 ms 44476 KB Output is correct
85 Correct 69 ms 44388 KB Output is correct
86 Correct 66 ms 44432 KB Output is correct
87 Correct 44 ms 44872 KB Output is correct
88 Correct 50 ms 44872 KB Output is correct
89 Correct 63 ms 44464 KB Output is correct
90 Correct 72 ms 44364 KB Output is correct
91 Correct 67 ms 44448 KB Output is correct
92 Correct 42 ms 44832 KB Output is correct
93 Correct 53 ms 44600 KB Output is correct
94 Correct 2 ms 1232 KB Output is correct
95 Correct 2 ms 1232 KB Output is correct
96 Correct 2 ms 1232 KB Output is correct
97 Correct 1 ms 1232 KB Output is correct
98 Correct 1 ms 1232 KB Output is correct
99 Correct 1 ms 1232 KB Output is correct
100 Correct 2 ms 1232 KB Output is correct
101 Correct 1 ms 1232 KB Output is correct
102 Correct 2 ms 1160 KB Output is correct
103 Correct 1 ms 1232 KB Output is correct
104 Correct 816 ms 39812 KB Output is correct
105 Correct 977 ms 44388 KB Output is correct
106 Correct 1053 ms 44384 KB Output is correct
107 Correct 844 ms 44396 KB Output is correct
108 Correct 1112 ms 44460 KB Output is correct
109 Correct 1057 ms 44368 KB Output is correct
110 Correct 1075 ms 44412 KB Output is correct
111 Correct 935 ms 44836 KB Output is correct
112 Correct 853 ms 44780 KB Output is correct
113 Correct 815 ms 44728 KB Output is correct
114 Correct 839 ms 44852 KB Output is correct

Subtask #7
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 423 ms 26520 KB Output is correct
2 Correct 736 ms 44872 KB Output is correct
3 Correct 930 ms 44840 KB Output is correct
4 Correct 944 ms 44884 KB Output is correct
5 Correct 879 ms 44900 KB Output is correct
6 Correct 766 ms 44856 KB Output is correct
7 Correct 822 ms 44888 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 1232 KB Output is correct
10 Correct 1 ms 1232 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 1232 KB Output is correct
13 Correct 1 ms 1232 KB Output is correct
14 Correct 1 ms 1232 KB Output is correct
15 Correct 1 ms 1232 KB Output is correct
16 Correct 2 ms 1232 KB Output is correct
17 Correct 1 ms 1232 KB Output is correct
18 Correct 1 ms 1232 KB Output is correct
19 Correct 1 ms 1232 KB Output is correct
20 Correct 1 ms 1232 KB Output is correct
21 Correct 2 ms 1356 KB Output is correct
22 Correct 0 ms 336 KB Output is correct
23 Correct 2 ms 1232 KB Output is correct
24 Correct 1 ms 1232 KB Output is correct
25 Correct 1 ms 1232 KB Output is correct
26 Correct 2 ms 1232 KB Output is correct
27 Correct 3 ms 1232 KB Output is correct
28 Correct 1 ms 1232 KB Output is correct
29 Correct 2 ms 1232 KB Output is correct
30 Correct 1 ms 1232 KB Output is correct
31 Correct 2 ms 1232 KB Output is correct
32 Correct 2 ms 1232 KB Output is correct
33 Correct 1 ms 1280 KB Output is correct
34 Correct 1 ms 1232 KB Output is correct
35 Correct 1 ms 720 KB Output is correct
36 Correct 1 ms 1232 KB Output is correct
37 Correct 2 ms 1232 KB Output is correct
38 Correct 1 ms 1232 KB Output is correct
39 Correct 1 ms 1232 KB Output is correct
40 Correct 2 ms 1232 KB Output is correct
41 Correct 2 ms 1232 KB Output is correct
42 Correct 1 ms 1232 KB Output is correct
43 Correct 1 ms 1232 KB Output is correct
44 Correct 1 ms 1232 KB Output is correct
45 Correct 2 ms 1232 KB Output is correct
46 Correct 41 ms 28580 KB Output is correct
47 Correct 71 ms 44396 KB Output is correct
48 Correct 64 ms 44460 KB Output is correct
49 Correct 65 ms 44428 KB Output is correct
50 Correct 69 ms 44440 KB Output is correct
51 Correct 65 ms 44456 KB Output is correct
52 Correct 64 ms 44352 KB Output is correct
53 Correct 44 ms 44836 KB Output is correct
54 Correct 56 ms 44796 KB Output is correct
55 Correct 56 ms 44712 KB Output is correct
56 Correct 48 ms 44660 KB Output is correct
57 Correct 61 ms 44444 KB Output is correct
58 Correct 64 ms 44552 KB Output is correct
59 Correct 79 ms 44456 KB Output is correct
60 Correct 44 ms 44872 KB Output is correct
61 Correct 43 ms 44836 KB Output is correct
62 Correct 65 ms 44464 KB Output is correct
63 Correct 79 ms 44340 KB Output is correct
64 Correct 65 ms 44452 KB Output is correct
65 Correct 42 ms 44852 KB Output is correct
66 Correct 55 ms 44616 KB Output is correct
67 Correct 64 ms 43052 KB Output is correct
68 Correct 70 ms 44408 KB Output is correct
69 Correct 62 ms 44472 KB Output is correct
70 Correct 67 ms 44440 KB Output is correct
71 Correct 68 ms 44528 KB Output is correct
72 Correct 68 ms 44384 KB Output is correct
73 Correct 65 ms 44440 KB Output is correct
74 Correct 51 ms 44816 KB Output is correct
75 Correct 42 ms 44872 KB Output is correct
76 Correct 53 ms 44748 KB Output is correct
77 Correct 48 ms 44852 KB Output is correct
78 Correct 773 ms 44196 KB Output is correct
79 Correct 1020 ms 44512 KB Output is correct
80 Correct 933 ms 44384 KB Output is correct
81 Correct 883 ms 44440 KB Output is correct
82 Correct 905 ms 44440 KB Output is correct
83 Correct 740 ms 44452 KB Output is correct
84 Correct 951 ms 44344 KB Output is correct
85 Correct 909 ms 44856 KB Output is correct
86 Correct 901 ms 44896 KB Output is correct
87 Correct 981 ms 44728 KB Output is correct
88 Correct 904 ms 44716 KB Output is correct
89 Correct 920 ms 44812 KB Output is correct
90 Correct 877 ms 44840 KB Output is correct
91 Correct 0 ms 336 KB Output is correct
92 Correct 2 ms 1232 KB Output is correct
93 Correct 1 ms 1232 KB Output is correct
94 Correct 63 ms 44476 KB Output is correct
95 Correct 69 ms 44388 KB Output is correct
96 Correct 66 ms 44432 KB Output is correct
97 Correct 44 ms 44872 KB Output is correct
98 Correct 50 ms 44872 KB Output is correct
99 Correct 63 ms 44464 KB Output is correct
100 Correct 72 ms 44364 KB Output is correct
101 Correct 67 ms 44448 KB Output is correct
102 Correct 42 ms 44832 KB Output is correct
103 Correct 53 ms 44600 KB Output is correct
104 Correct 2 ms 1232 KB Output is correct
105 Correct 2 ms 1232 KB Output is correct
106 Correct 2 ms 1232 KB Output is correct
107 Correct 1 ms 1232 KB Output is correct
108 Correct 1 ms 1232 KB Output is correct
109 Correct 1 ms 1232 KB Output is correct
110 Correct 2 ms 1232 KB Output is correct
111 Correct 1 ms 1232 KB Output is correct
112 Correct 2 ms 1160 KB Output is correct
113 Correct 1 ms 1232 KB Output is correct
114 Correct 318 ms 10828 KB Output is correct
115 Correct 846 ms 44380 KB Output is correct
116 Correct 986 ms 44476 KB Output is correct
117 Correct 919 ms 44360 KB Output is correct
118 Correct 979 ms 44356 KB Output is correct
119 Correct 830 ms 44444 KB Output is correct
120 Correct 985 ms 44360 KB Output is correct
121 Correct 926 ms 44860 KB Output is correct
122 Correct 727 ms 44832 KB Output is correct
123 Correct 917 ms 44688 KB Output is correct
124 Correct 840 ms 44716 KB Output is correct
125 Correct 63 ms 44364 KB Output is correct
126 Correct 65 ms 44384 KB Output is correct
127 Correct 65 ms 44360 KB Output is correct
128 Correct 42 ms 44848 KB Output is correct
129 Correct 55 ms 44588 KB Output is correct
130 Correct 80 ms 43032 KB Output is correct
131 Correct 65 ms 44364 KB Output is correct
132 Correct 65 ms 44452 KB Output is correct
133 Correct 65 ms 44468 KB Output is correct
134 Correct 69 ms 44460 KB Output is correct
135 Correct 73 ms 44376 KB Output is correct
136 Correct 67 ms 44464 KB Output is correct
137 Correct 43 ms 44884 KB Output is correct
138 Correct 41 ms 44900 KB Output is correct
139 Correct 70 ms 44632 KB Output is correct
140 Correct 45 ms 44844 KB Output is correct
141 Correct 1 ms 1232 KB Output is correct
142 Correct 2 ms 1232 KB Output is correct
143 Correct 2 ms 1232 KB Output is correct
144 Correct 1 ms 1232 KB Output is correct
145 Correct 1 ms 1232 KB Output is correct
146 Correct 1 ms 720 KB Output is correct
147 Correct 2 ms 1232 KB Output is correct
148 Correct 2 ms 1232 KB Output is correct
149 Correct 2 ms 1232 KB Output is correct
150 Correct 2 ms 1232 KB Output is correct
151 Correct 2 ms 1232 KB Output is correct
152 Correct 1 ms 1232 KB Output is correct
153 Correct 1 ms 1232 KB Output is correct
154 Correct 1 ms 1232 KB Output is correct
155 Correct 1 ms 1232 KB Output is correct
156 Correct 1 ms 1232 KB Output is correct
157 Correct 816 ms 39812 KB Output is correct
158 Correct 977 ms 44388 KB Output is correct
159 Correct 1053 ms 44384 KB Output is correct
160 Correct 844 ms 44396 KB Output is correct
161 Correct 1112 ms 44460 KB Output is correct
162 Correct 1057 ms 44368 KB Output is correct
163 Correct 1075 ms 44412 KB Output is correct
164 Correct 935 ms 44836 KB Output is correct
165 Correct 853 ms 44780 KB Output is correct
166 Correct 815 ms 44728 KB Output is correct
167 Correct 839 ms 44852 KB Output is correct
168 Correct 0 ms 336 KB Output is correct
169 Correct 567 ms 16052 KB Output is correct
170 Correct 1199 ms 44452 KB Output is correct
171 Correct 1215 ms 44488 KB Output is correct
172 Correct 973 ms 44348 KB Output is correct
173 Correct 1191 ms 44444 KB Output is correct
174 Correct 1020 ms 44360 KB Output is correct
175 Correct 1223 ms 44408 KB Output is correct
176 Correct 887 ms 44836 KB Output is correct
177 Correct 821 ms 44828 KB Output is correct
178 Correct 856 ms 44836 KB Output is correct
179 Correct 1029 ms 44576 KB Output is correct