oj.uz

Submission #568035

# Submission time Handle Problem Language Result Execution time Memory
568035 2022-05-24T14:17:39 Z MohamedAhmed04 Interval Collection (CCO20_day2problem2) C++17
25 / 25
 6341 ms 281564 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e6 + 10 ;

int tree[2][2 * MAX + 100] ;
int val[2][MAX] ;

int tmp[2] = {(int)1e9 , (int)-1e9} ;

void build(bool t)
{
	for(int i = 2*MAX ; i >= 0 ; --i)
		tree[t][i] = tmp[t] ;
}

void update(int idx , int val , bool t)
{
	for(tree[t][idx += MAX] = val ; idx > 1 ; idx >>= 1)
	{
		if(!t)
			tree[t][idx >> 1] = min(tree[t][idx] , tree[t][idx^1]) ;
		else
			tree[t][idx >> 1] = max(tree[t][idx] , tree[t][idx^1]) ;
	}
}

int query(int l , int r , bool t)
{
	++r ;
	int ans = tmp[t] ;
	for(l += MAX , r += MAX ; l < r ; l >>= 1 , r >>= 1)
	{
		if(l & 1)
		{
			if(!t)
				ans = min(ans , tree[t][l++]) ;
			else
				ans = max(ans , tree[t][l++]) ;
		}
		if(r & 1)
		{
			if(!t)
				ans = min(ans , tree[t][--r]) ;
			else
				ans = max(ans , tree[t][--r]) ;
		}
	}
	return ans ;
}

int q ;

set<int>sl[MAX] , sr[MAX] ;

pair<int , int>calc(int l , int r)
{
	pair<int , int>p = {r-l , r-l} ;
	if(tree[0][1] <= l)
	{
		int x = query(1 , l , 1) ;
		p = min(p , make_pair(0 , r - x)) ;
	}
	if(tree[1][1] >= r)
	{
		int x = query(r , MAX , 0) ;
		p = min(p , make_pair(0 , x - l)) ;
	}
	if(p.first)
	{
		int x = val[1][tree[0][1]] ;
		p = min(p , make_pair(tree[0][1] - l , r - x)) ;

		x = val[0][tree[1][1]] ;
		p = min(p , make_pair(r - tree[1][1] , x - l)) ;
	}
	return p ;
}

char c[MAX] ;
int L[MAX] , R[MAX] , id[MAX] ;
int ans[MAX] ;

vector< pair<int , int> >tree2[2 * MAX] ;

void Add(int node , int l , int r , int from , int to)
{
	if(from > r || to < l)
		return ;
	if(l >= from && r <= to)
	{
		tree2[node].emplace_back(L[from] , R[from]) ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	Add(node << 1 , l , mid , from , to) ;
	Add(node << 1 | 1 , mid+1 , r , from , to) ;
}

void solve(int node , int st , int en , pair<int , int>best)
{
	if(st > en)
		return ;
	pair<int , int>best2 = best ;
	for(auto &p : tree2[node])
	{
		int l = p.first , r = p.second ;
		sl[l].insert(r) ;
		sr[r].insert(l) ;
		int x = val[0][l] , y = val[1][r] ;
		val[0][l] = *sl[l].begin() , val[1][r] = *sr[r].rbegin() ;
		if(x != val[0][l])
			update(l , val[0][l] , 0) ;
		if(y != val[1][r]) 
			update(r , val[1][r] , 1) ;
		best2 = min(best2 , calc(l , r)) ;
	}
	int mid = (st + en) >> 1 ;
	if(st == en)
		ans[st] = best2.second ;
	else
		solve(node << 1 , st , mid , best2) , solve(node << 1 | 1 , mid+1 , en , best2) ;
	for(auto &p : tree2[node])
	{
		int l = p.first , r = p.second ;
		sl[l].erase(r) ;
		sr[r].erase(l) ;
		int x = val[0][l] , y = val[1][r] ;
		val[0][l] = tmp[0] ;
		if(sl[l].size())
			val[0][l] = *sl[l].begin() ;
		val[1][r] = tmp[1] ;
		if(sr[r].size())
			val[1][r] = *sr[r].rbegin() ;
		if(x != val[0][l])
			update(l , val[0][l] , 0) ;
		if(y != val[1][r])
			update(r , val[1][r] , 1) ;
	}
}

void pre_id()
{
	vector< pair<int , int> >vp ;
	for(int i = 1 ; i <= q ; ++i)
		vp.emplace_back(L[i] , R[i]) ;
	sort(vp.begin() , vp.end()) ;
	vp.erase(unique(vp.begin() , vp.end()) , vp.end()) ;
	for(int i = 1 ; i <= q ; ++i)
	{
		id[i] = lower_bound(vp.begin() , vp.end() , make_pair(L[i] , R[i])) - vp.begin() ;
		id[i]++ ;
	}
}

int freq[MAX] , prv[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	build(0) , build(1) ;
	cin>>q ;
	for(int i = 1 ; i <= q ; ++i)
		cin>>c[i]>>L[i]>>R[i] ;
	pre_id() ;
	for(int i = 1 ; i <= q ; ++i)
	{
		if(c[i] == 'A')
		{
			if(!freq[id[i]])
				prv[id[i]] = i ;
			freq[id[i]]++ ;
		}
		else if(c[i] == 'R')
		{
			freq[id[i]]-- ;
			if(!freq[id[i]])
				Add(1 , 1 , q , prv[id[i]] , i-1) ;
		}
	}
	for(int i = 1 ; i <= q ; ++i)
	{
		if(freq[id[i]])
		{
			Add(1 , 1 , q , prv[id[i]] , q) ;
			freq[id[i]] = 0 ;
		}
	}
	solve(1 , 1 , q , {2e9 , 2e9}) ;
	for(int i = 1 ; i <= q ; ++i)
		cout<<ans[i]<<"\n" ;
	return 0 ;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 159052 KB Output is correct
2 Correct 76 ms 158672 KB Output is correct
3 Correct 83 ms 158540 KB Output is correct
4 Correct 78 ms 158548 KB Output is correct
5 Correct 86 ms 159064 KB Output is correct
6 Correct 79 ms 158668 KB Output is correct
7 Correct 78 ms 158552 KB Output is correct
8 Correct 79 ms 158684 KB Output is correct
9 Correct 87 ms 159384 KB Output is correct
10 Correct 81 ms 159264 KB Output is correct
11 Correct 80 ms 159240 KB Output is correct
12 Correct 79 ms 159248 KB Output is correct
13 Correct 82 ms 159692 KB Output is correct
14 Correct 83 ms 159700 KB Output is correct
15 Correct 80 ms 159564 KB Output is correct
16 Correct 81 ms 159628 KB Output is correct
17 Correct 80 ms 158952 KB Output is correct
18 Correct 88 ms 158556 KB Output is correct
19 Correct 83 ms 158608 KB Output is correct
20 Correct 78 ms 158556 KB Output is correct
21 Correct 84 ms 158860 KB Output is correct
22 Correct 81 ms 158600 KB Output is correct
23 Correct 81 ms 158428 KB Output is correct
24 Correct 78 ms 158572 KB Output is correct
25 Correct 79 ms 159548 KB Output is correct
26 Correct 79 ms 159052 KB Output is correct
27 Correct 79 ms 159088 KB Output is correct
28 Correct 81 ms 159020 KB Output is correct
29 Correct 84 ms 159404 KB Output is correct
30 Correct 80 ms 159468 KB Output is correct
31 Correct 87 ms 159564 KB Output is correct
32 Correct 83 ms 159472 KB Output is correct
33 Correct 78 ms 158436 KB Output is correct
34 Correct 79 ms 158540 KB Output is correct
35 Correct 82 ms 158532 KB Output is correct
36 Correct 80 ms 158564 KB Output is correct
37 Correct 83 ms 158668 KB Output is correct
38 Correct 80 ms 158656 KB Output is correct
39 Correct 78 ms 158480 KB Output is correct
40 Correct 79 ms 158584 KB Output is correct
41 Correct 80 ms 158884 KB Output is correct
42 Correct 80 ms 158540 KB Output is correct
43 Correct 81 ms 158508 KB Output is correct
44 Correct 78 ms 158472 KB Output is correct
45 Correct 79 ms 158524 KB Output is correct
46 Correct 88 ms 158512 KB Output is correct
47 Correct 79 ms 158576 KB Output is correct
48 Correct 79 ms 158600 KB Output is correct
49 Correct 79 ms 157376 KB Output is correct
50 Correct 80 ms 157408 KB Output is correct
51 Correct 80 ms 157452 KB Output is correct
52 Correct 78 ms 157432 KB Output is correct
53 Correct 79 ms 157396 KB Output is correct
54 Correct 79 ms 157388 KB Output is correct
55 Correct 79 ms 157476 KB Output is correct
56 Correct 80 ms 157416 KB Output is correct
57 Correct 79 ms 157464 KB Output is correct
58 Correct 81 ms 157420 KB Output is correct
59 Correct 81 ms 157884 KB Output is correct
60 Correct 85 ms 157964 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 159052 KB Output is correct
2 Correct 76 ms 158672 KB Output is correct
3 Correct 83 ms 158540 KB Output is correct
4 Correct 78 ms 158548 KB Output is correct
5 Correct 86 ms 159064 KB Output is correct
6 Correct 79 ms 158668 KB Output is correct
7 Correct 78 ms 158552 KB Output is correct
8 Correct 79 ms 158684 KB Output is correct
9 Correct 87 ms 159384 KB Output is correct
10 Correct 81 ms 159264 KB Output is correct
11 Correct 80 ms 159240 KB Output is correct
12 Correct 79 ms 159248 KB Output is correct
13 Correct 82 ms 159692 KB Output is correct
14 Correct 83 ms 159700 KB Output is correct
15 Correct 80 ms 159564 KB Output is correct
16 Correct 81 ms 159628 KB Output is correct
17 Correct 80 ms 158952 KB Output is correct
18 Correct 88 ms 158556 KB Output is correct
19 Correct 83 ms 158608 KB Output is correct
20 Correct 78 ms 158556 KB Output is correct
21 Correct 84 ms 158860 KB Output is correct
22 Correct 81 ms 158600 KB Output is correct
23 Correct 81 ms 158428 KB Output is correct
24 Correct 78 ms 158572 KB Output is correct
25 Correct 79 ms 159548 KB Output is correct
26 Correct 79 ms 159052 KB Output is correct
27 Correct 79 ms 159088 KB Output is correct
28 Correct 81 ms 159020 KB Output is correct
29 Correct 84 ms 159404 KB Output is correct
30 Correct 80 ms 159468 KB Output is correct
31 Correct 87 ms 159564 KB Output is correct
32 Correct 83 ms 159472 KB Output is correct
33 Correct 78 ms 158436 KB Output is correct
34 Correct 79 ms 158540 KB Output is correct
35 Correct 82 ms 158532 KB Output is correct
36 Correct 80 ms 158564 KB Output is correct
37 Correct 83 ms 158668 KB Output is correct
38 Correct 80 ms 158656 KB Output is correct
39 Correct 78 ms 158480 KB Output is correct
40 Correct 79 ms 158584 KB Output is correct
41 Correct 80 ms 158884 KB Output is correct
42 Correct 80 ms 158540 KB Output is correct
43 Correct 81 ms 158508 KB Output is correct
44 Correct 78 ms 158472 KB Output is correct
45 Correct 79 ms 158524 KB Output is correct
46 Correct 88 ms 158512 KB Output is correct
47 Correct 79 ms 158576 KB Output is correct
48 Correct 79 ms 158600 KB Output is correct
49 Correct 79 ms 157376 KB Output is correct
50 Correct 80 ms 157408 KB Output is correct
51 Correct 80 ms 157452 KB Output is correct
52 Correct 78 ms 157432 KB Output is correct
53 Correct 79 ms 157396 KB Output is correct
54 Correct 79 ms 157388 KB Output is correct
55 Correct 79 ms 157476 KB Output is correct
56 Correct 80 ms 157416 KB Output is correct
57 Correct 79 ms 157464 KB Output is correct
58 Correct 81 ms 157420 KB Output is correct
59 Correct 81 ms 157884 KB Output is correct
60 Correct 85 ms 157964 KB Output is correct
61 Correct 82 ms 156896 KB Output is correct
62 Correct 79 ms 156992 KB Output is correct
63 Correct 78 ms 156864 KB Output is correct
64 Correct 145 ms 166016 KB Output is correct
65 Correct 129 ms 165300 KB Output is correct
66 Correct 114 ms 164904 KB Output is correct
67 Correct 94 ms 164428 KB Output is correct
68 Correct 150 ms 166220 KB Output is correct
69 Correct 128 ms 165280 KB Output is correct
70 Correct 117 ms 164976 KB Output is correct
71 Correct 108 ms 164812 KB Output is correct
72 Correct 150 ms 166716 KB Output is correct
73 Correct 145 ms 166384 KB Output is correct
74 Correct 146 ms 166340 KB Output is correct
75 Correct 140 ms 166260 KB Output is correct
76 Correct 156 ms 166952 KB Output is correct
77 Correct 153 ms 166868 KB Output is correct
78 Correct 155 ms 166728 KB Output is correct
79 Correct 150 ms 166960 KB Output is correct
80 Correct 151 ms 166524 KB Output is correct
81 Correct 130 ms 165744 KB Output is correct
82 Correct 112 ms 165328 KB Output is correct
83 Correct 92 ms 164468 KB Output is correct
84 Correct 143 ms 166536 KB Output is correct
85 Correct 130 ms 165832 KB Output is correct
86 Correct 117 ms 165404 KB Output is correct
87 Correct 109 ms 165492 KB Output is correct
88 Correct 150 ms 166896 KB Output is correct
89 Correct 144 ms 166832 KB Output is correct
90 Correct 150 ms 166768 KB Output is correct
91 Correct 146 ms 166876 KB Output is correct
92 Correct 150 ms 167184 KB Output is correct
93 Correct 157 ms 167268 KB Output is correct
94 Correct 152 ms 167276 KB Output is correct
95 Correct 156 ms 167288 KB Output is correct
96 Correct 91 ms 164416 KB Output is correct
97 Correct 94 ms 164476 KB Output is correct
98 Correct 92 ms 164344 KB Output is correct
99 Correct 93 ms 164388 KB Output is correct
100 Correct 119 ms 164916 KB Output is correct
101 Correct 102 ms 164624 KB Output is correct
102 Correct 107 ms 164740 KB Output is correct
103 Correct 95 ms 164512 KB Output is correct
104 Correct 150 ms 165936 KB Output is correct
105 Correct 126 ms 165208 KB Output is correct
106 Correct 110 ms 164848 KB Output is correct
107 Correct 98 ms 164648 KB Output is correct
108 Correct 148 ms 165672 KB Output is correct
109 Correct 133 ms 165100 KB Output is correct
110 Correct 114 ms 164880 KB Output is correct
111 Correct 97 ms 164480 KB Output is correct
112 Correct 104 ms 162420 KB Output is correct
113 Correct 105 ms 162508 KB Output is correct
114 Correct 98 ms 162436 KB Output is correct
115 Correct 107 ms 162448 KB Output is correct
116 Correct 100 ms 162396 KB Output is correct
117 Correct 105 ms 162524 KB Output is correct
118 Correct 98 ms 162416 KB Output is correct
119 Correct 104 ms 162428 KB Output is correct
120 Correct 98 ms 162372 KB Output is correct
121 Correct 105 ms 162508 KB Output is correct
122 Correct 130 ms 167424 KB Output is correct
123 Correct 123 ms 167276 KB Output is correct
124 Correct 132 ms 158628 KB Output is correct
125 Correct 107 ms 158176 KB Output is correct
126 Correct 101 ms 158152 KB Output is correct
127 Correct 113 ms 158832 KB Output is correct
128 Correct 108 ms 158212 KB Output is correct
129 Correct 103 ms 158160 KB Output is correct
130 Correct 113 ms 158964 KB Output is correct
131 Correct 107 ms 158404 KB Output is correct
132 Correct 101 ms 158116 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 159052 KB Output is correct
2 Correct 76 ms 158672 KB Output is correct
3 Correct 83 ms 158540 KB Output is correct
4 Correct 78 ms 158548 KB Output is correct
5 Correct 86 ms 159064 KB Output is correct
6 Correct 79 ms 158668 KB Output is correct
7 Correct 78 ms 158552 KB Output is correct
8 Correct 79 ms 158684 KB Output is correct
9 Correct 87 ms 159384 KB Output is correct
10 Correct 81 ms 159264 KB Output is correct
11 Correct 80 ms 159240 KB Output is correct
12 Correct 79 ms 159248 KB Output is correct
13 Correct 82 ms 159692 KB Output is correct
14 Correct 83 ms 159700 KB Output is correct
15 Correct 80 ms 159564 KB Output is correct
16 Correct 81 ms 159628 KB Output is correct
17 Correct 80 ms 158952 KB Output is correct
18 Correct 88 ms 158556 KB Output is correct
19 Correct 83 ms 158608 KB Output is correct
20 Correct 78 ms 158556 KB Output is correct
21 Correct 84 ms 158860 KB Output is correct
22 Correct 81 ms 158600 KB Output is correct
23 Correct 81 ms 158428 KB Output is correct
24 Correct 78 ms 158572 KB Output is correct
25 Correct 79 ms 159548 KB Output is correct
26 Correct 79 ms 159052 KB Output is correct
27 Correct 79 ms 159088 KB Output is correct
28 Correct 81 ms 159020 KB Output is correct
29 Correct 84 ms 159404 KB Output is correct
30 Correct 80 ms 159468 KB Output is correct
31 Correct 87 ms 159564 KB Output is correct
32 Correct 83 ms 159472 KB Output is correct
33 Correct 78 ms 158436 KB Output is correct
34 Correct 79 ms 158540 KB Output is correct
35 Correct 82 ms 158532 KB Output is correct
36 Correct 80 ms 158564 KB Output is correct
37 Correct 83 ms 158668 KB Output is correct
38 Correct 80 ms 158656 KB Output is correct
39 Correct 78 ms 158480 KB Output is correct
40 Correct 79 ms 158584 KB Output is correct
41 Correct 80 ms 158884 KB Output is correct
42 Correct 80 ms 158540 KB Output is correct
43 Correct 81 ms 158508 KB Output is correct
44 Correct 78 ms 158472 KB Output is correct
45 Correct 79 ms 158524 KB Output is correct
46 Correct 88 ms 158512 KB Output is correct
47 Correct 79 ms 158576 KB Output is correct
48 Correct 79 ms 158600 KB Output is correct
49 Correct 79 ms 157376 KB Output is correct
50 Correct 80 ms 157408 KB Output is correct
51 Correct 80 ms 157452 KB Output is correct
52 Correct 78 ms 157432 KB Output is correct
53 Correct 79 ms 157396 KB Output is correct
54 Correct 79 ms 157388 KB Output is correct
55 Correct 79 ms 157476 KB Output is correct
56 Correct 80 ms 157416 KB Output is correct
57 Correct 79 ms 157464 KB Output is correct
58 Correct 81 ms 157420 KB Output is correct
59 Correct 81 ms 157884 KB Output is correct
60 Correct 85 ms 157964 KB Output is correct
61 Correct 82 ms 156896 KB Output is correct
62 Correct 79 ms 156992 KB Output is correct
63 Correct 78 ms 156864 KB Output is correct
64 Correct 145 ms 166016 KB Output is correct
65 Correct 129 ms 165300 KB Output is correct
66 Correct 114 ms 164904 KB Output is correct
67 Correct 94 ms 164428 KB Output is correct
68 Correct 150 ms 166220 KB Output is correct
69 Correct 128 ms 165280 KB Output is correct
70 Correct 117 ms 164976 KB Output is correct
71 Correct 108 ms 164812 KB Output is correct
72 Correct 150 ms 166716 KB Output is correct
73 Correct 145 ms 166384 KB Output is correct
74 Correct 146 ms 166340 KB Output is correct
75 Correct 140 ms 166260 KB Output is correct
76 Correct 156 ms 166952 KB Output is correct
77 Correct 153 ms 166868 KB Output is correct
78 Correct 155 ms 166728 KB Output is correct
79 Correct 150 ms 166960 KB Output is correct
80 Correct 151 ms 166524 KB Output is correct
81 Correct 130 ms 165744 KB Output is correct
82 Correct 112 ms 165328 KB Output is correct
83 Correct 92 ms 164468 KB Output is correct
84 Correct 143 ms 166536 KB Output is correct
85 Correct 130 ms 165832 KB Output is correct
86 Correct 117 ms 165404 KB Output is correct
87 Correct 109 ms 165492 KB Output is correct
88 Correct 150 ms 166896 KB Output is correct
89 Correct 144 ms 166832 KB Output is correct
90 Correct 150 ms 166768 KB Output is correct
91 Correct 146 ms 166876 KB Output is correct
92 Correct 150 ms 167184 KB Output is correct
93 Correct 157 ms 167268 KB Output is correct
94 Correct 152 ms 167276 KB Output is correct
95 Correct 156 ms 167288 KB Output is correct
96 Correct 91 ms 164416 KB Output is correct
97 Correct 94 ms 164476 KB Output is correct
98 Correct 92 ms 164344 KB Output is correct
99 Correct 93 ms 164388 KB Output is correct
100 Correct 119 ms 164916 KB Output is correct
101 Correct 102 ms 164624 KB Output is correct
102 Correct 107 ms 164740 KB Output is correct
103 Correct 95 ms 164512 KB Output is correct
104 Correct 150 ms 165936 KB Output is correct
105 Correct 126 ms 165208 KB Output is correct
106 Correct 110 ms 164848 KB Output is correct
107 Correct 98 ms 164648 KB Output is correct
108 Correct 148 ms 165672 KB Output is correct
109 Correct 133 ms 165100 KB Output is correct
110 Correct 114 ms 164880 KB Output is correct
111 Correct 97 ms 164480 KB Output is correct
112 Correct 104 ms 162420 KB Output is correct
113 Correct 105 ms 162508 KB Output is correct
114 Correct 98 ms 162436 KB Output is correct
115 Correct 107 ms 162448 KB Output is correct
116 Correct 100 ms 162396 KB Output is correct
117 Correct 105 ms 162524 KB Output is correct
118 Correct 98 ms 162416 KB Output is correct
119 Correct 104 ms 162428 KB Output is correct
120 Correct 98 ms 162372 KB Output is correct
121 Correct 105 ms 162508 KB Output is correct
122 Correct 130 ms 167424 KB Output is correct
123 Correct 123 ms 167276 KB Output is correct
124 Correct 132 ms 158628 KB Output is correct
125 Correct 107 ms 158176 KB Output is correct
126 Correct 101 ms 158152 KB Output is correct
127 Correct 113 ms 158832 KB Output is correct
128 Correct 108 ms 158212 KB Output is correct
129 Correct 103 ms 158160 KB Output is correct
130 Correct 113 ms 158964 KB Output is correct
131 Correct 107 ms 158404 KB Output is correct
132 Correct 101 ms 158116 KB Output is correct
133 Correct 442 ms 173292 KB Output is correct
134 Correct 337 ms 171096 KB Output is correct
135 Correct 255 ms 170340 KB Output is correct
136 Correct 145 ms 167956 KB Output is correct
137 Correct 446 ms 173356 KB Output is correct
138 Correct 357 ms 171016 KB Output is correct
139 Correct 275 ms 169984 KB Output is correct
140 Correct 204 ms 169140 KB Output is correct
141 Correct 493 ms 174944 KB Output is correct
142 Correct 440 ms 174256 KB Output is correct
143 Correct 407 ms 174088 KB Output is correct
144 Correct 412 ms 174012 KB Output is correct
145 Correct 459 ms 175804 KB Output is correct
146 Correct 466 ms 175748 KB Output is correct
147 Correct 480 ms 175724 KB Output is correct
148 Correct 461 ms 175672 KB Output is correct
149 Correct 438 ms 173564 KB Output is correct
150 Correct 342 ms 171292 KB Output is correct
151 Correct 259 ms 170276 KB Output is correct
152 Correct 144 ms 168196 KB Output is correct
153 Correct 424 ms 173392 KB Output is correct
154 Correct 348 ms 171188 KB Output is correct
155 Correct 261 ms 170280 KB Output is correct
156 Correct 210 ms 169332 KB Output is correct
157 Correct 469 ms 175196 KB Output is correct
158 Correct 439 ms 174576 KB Output is correct
159 Correct 412 ms 174388 KB Output is correct
160 Correct 489 ms 174240 KB Output is correct
161 Correct 464 ms 175728 KB Output is correct
162 Correct 451 ms 175764 KB Output is correct
163 Correct 452 ms 175884 KB Output is correct
164 Correct 449 ms 175980 KB Output is correct
165 Correct 128 ms 167404 KB Output is correct
166 Correct 133 ms 167372 KB Output is correct
167 Correct 129 ms 167448 KB Output is correct
168 Correct 133 ms 167364 KB Output is correct
169 Correct 214 ms 169272 KB Output is correct
170 Correct 186 ms 168756 KB Output is correct
171 Correct 176 ms 168636 KB Output is correct
172 Correct 139 ms 167660 KB Output is correct
173 Correct 507 ms 173436 KB Output is correct
174 Correct 332 ms 170792 KB Output is correct
175 Correct 263 ms 169780 KB Output is correct
176 Correct 139 ms 167620 KB Output is correct
177 Correct 422 ms 172896 KB Output is correct
178 Correct 327 ms 170384 KB Output is correct
179 Correct 238 ms 169448 KB Output is correct
180 Correct 144 ms 167760 KB Output is correct
181 Correct 164 ms 168092 KB Output is correct
182 Correct 220 ms 168060 KB Output is correct
183 Correct 177 ms 167744 KB Output is correct
184 Correct 209 ms 167740 KB Output is correct
185 Correct 169 ms 168040 KB Output is correct
186 Correct 213 ms 168012 KB Output is correct
187 Correct 162 ms 167788 KB Output is correct
188 Correct 210 ms 167752 KB Output is correct
189 Correct 166 ms 168088 KB Output is correct
190 Correct 209 ms 168104 KB Output is correct
191 Correct 262 ms 175700 KB Output is correct
192 Correct 282 ms 175604 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 209040 KB Output is correct
2 Correct 768 ms 208992 KB Output is correct
3 Correct 1413 ms 254556 KB Output is correct
4 Correct 1383 ms 254660 KB Output is correct
5 Correct 1628 ms 273428 KB Output is correct
6 Correct 1674 ms 273308 KB Output is correct
7 Correct 2285 ms 215884 KB Output is correct
8 Correct 1551 ms 209816 KB Output is correct
9 Correct 1488 ms 208644 KB Output is correct
10 Correct 2602 ms 220256 KB Output is correct
11 Correct 1563 ms 209980 KB Output is correct
12 Correct 1477 ms 208832 KB Output is correct
13 Correct 2765 ms 221936 KB Output is correct
14 Correct 1562 ms 209944 KB Output is correct
15 Correct 1524 ms 208768 KB Output is correct
16 Correct 1059 ms 199872 KB Output is correct
17 Correct 1020 ms 199784 KB Output is correct
18 Correct 1076 ms 199872 KB Output is correct
19 Correct 1137 ms 200120 KB Output is correct
20 Correct 1119 ms 199920 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 159052 KB Output is correct
2 Correct 76 ms 158672 KB Output is correct
3 Correct 83 ms 158540 KB Output is correct
4 Correct 78 ms 158548 KB Output is correct
5 Correct 86 ms 159064 KB Output is correct
6 Correct 79 ms 158668 KB Output is correct
7 Correct 78 ms 158552 KB Output is correct
8 Correct 79 ms 158684 KB Output is correct
9 Correct 87 ms 159384 KB Output is correct
10 Correct 81 ms 159264 KB Output is correct
11 Correct 80 ms 159240 KB Output is correct
12 Correct 79 ms 159248 KB Output is correct
13 Correct 82 ms 159692 KB Output is correct
14 Correct 83 ms 159700 KB Output is correct
15 Correct 80 ms 159564 KB Output is correct
16 Correct 81 ms 159628 KB Output is correct
17 Correct 80 ms 158952 KB Output is correct
18 Correct 88 ms 158556 KB Output is correct
19 Correct 83 ms 158608 KB Output is correct
20 Correct 78 ms 158556 KB Output is correct
21 Correct 84 ms 158860 KB Output is correct
22 Correct 81 ms 158600 KB Output is correct
23 Correct 81 ms 158428 KB Output is correct
24 Correct 78 ms 158572 KB Output is correct
25 Correct 79 ms 159548 KB Output is correct
26 Correct 79 ms 159052 KB Output is correct
27 Correct 79 ms 159088 KB Output is correct
28 Correct 81 ms 159020 KB Output is correct
29 Correct 84 ms 159404 KB Output is correct
30 Correct 80 ms 159468 KB Output is correct
31 Correct 87 ms 159564 KB Output is correct
32 Correct 83 ms 159472 KB Output is correct
33 Correct 78 ms 158436 KB Output is correct
34 Correct 79 ms 158540 KB Output is correct
35 Correct 82 ms 158532 KB Output is correct
36 Correct 80 ms 158564 KB Output is correct
37 Correct 83 ms 158668 KB Output is correct
38 Correct 80 ms 158656 KB Output is correct
39 Correct 78 ms 158480 KB Output is correct
40 Correct 79 ms 158584 KB Output is correct
41 Correct 80 ms 158884 KB Output is correct
42 Correct 80 ms 158540 KB Output is correct
43 Correct 81 ms 158508 KB Output is correct
44 Correct 78 ms 158472 KB Output is correct
45 Correct 79 ms 158524 KB Output is correct
46 Correct 88 ms 158512 KB Output is correct
47 Correct 79 ms 158576 KB Output is correct
48 Correct 79 ms 158600 KB Output is correct
49 Correct 79 ms 157376 KB Output is correct
50 Correct 80 ms 157408 KB Output is correct
51 Correct 80 ms 157452 KB Output is correct
52 Correct 78 ms 157432 KB Output is correct
53 Correct 79 ms 157396 KB Output is correct
54 Correct 79 ms 157388 KB Output is correct
55 Correct 79 ms 157476 KB Output is correct
56 Correct 80 ms 157416 KB Output is correct
57 Correct 79 ms 157464 KB Output is correct
58 Correct 81 ms 157420 KB Output is correct
59 Correct 81 ms 157884 KB Output is correct
60 Correct 85 ms 157964 KB Output is correct
61 Correct 82 ms 156896 KB Output is correct
62 Correct 79 ms 156992 KB Output is correct
63 Correct 78 ms 156864 KB Output is correct
64 Correct 145 ms 166016 KB Output is correct
65 Correct 129 ms 165300 KB Output is correct
66 Correct 114 ms 164904 KB Output is correct
67 Correct 94 ms 164428 KB Output is correct
68 Correct 150 ms 166220 KB Output is correct
69 Correct 128 ms 165280 KB Output is correct
70 Correct 117 ms 164976 KB Output is correct
71 Correct 108 ms 164812 KB Output is correct
72 Correct 150 ms 166716 KB Output is correct
73 Correct 145 ms 166384 KB Output is correct
74 Correct 146 ms 166340 KB Output is correct
75 Correct 140 ms 166260 KB Output is correct
76 Correct 156 ms 166952 KB Output is correct
77 Correct 153 ms 166868 KB Output is correct
78 Correct 155 ms 166728 KB Output is correct
79 Correct 150 ms 166960 KB Output is correct
80 Correct 151 ms 166524 KB Output is correct
81 Correct 130 ms 165744 KB Output is correct
82 Correct 112 ms 165328 KB Output is correct
83 Correct 92 ms 164468 KB Output is correct
84 Correct 143 ms 166536 KB Output is correct
85 Correct 130 ms 165832 KB Output is correct
86 Correct 117 ms 165404 KB Output is correct
87 Correct 109 ms 165492 KB Output is correct
88 Correct 150 ms 166896 KB Output is correct
89 Correct 144 ms 166832 KB Output is correct
90 Correct 150 ms 166768 KB Output is correct
91 Correct 146 ms 166876 KB Output is correct
92 Correct 150 ms 167184 KB Output is correct
93 Correct 157 ms 167268 KB Output is correct
94 Correct 152 ms 167276 KB Output is correct
95 Correct 156 ms 167288 KB Output is correct
96 Correct 91 ms 164416 KB Output is correct
97 Correct 94 ms 164476 KB Output is correct
98 Correct 92 ms 164344 KB Output is correct
99 Correct 93 ms 164388 KB Output is correct
100 Correct 119 ms 164916 KB Output is correct
101 Correct 102 ms 164624 KB Output is correct
102 Correct 107 ms 164740 KB Output is correct
103 Correct 95 ms 164512 KB Output is correct
104 Correct 150 ms 165936 KB Output is correct
105 Correct 126 ms 165208 KB Output is correct
106 Correct 110 ms 164848 KB Output is correct
107 Correct 98 ms 164648 KB Output is correct
108 Correct 148 ms 165672 KB Output is correct
109 Correct 133 ms 165100 KB Output is correct
110 Correct 114 ms 164880 KB Output is correct
111 Correct 97 ms 164480 KB Output is correct
112 Correct 104 ms 162420 KB Output is correct
113 Correct 105 ms 162508 KB Output is correct
114 Correct 98 ms 162436 KB Output is correct
115 Correct 107 ms 162448 KB Output is correct
116 Correct 100 ms 162396 KB Output is correct
117 Correct 105 ms 162524 KB Output is correct
118 Correct 98 ms 162416 KB Output is correct
119 Correct 104 ms 162428 KB Output is correct
120 Correct 98 ms 162372 KB Output is correct
121 Correct 105 ms 162508 KB Output is correct
122 Correct 130 ms 167424 KB Output is correct
123 Correct 123 ms 167276 KB Output is correct
124 Correct 132 ms 158628 KB Output is correct
125 Correct 107 ms 158176 KB Output is correct
126 Correct 101 ms 158152 KB Output is correct
127 Correct 113 ms 158832 KB Output is correct
128 Correct 108 ms 158212 KB Output is correct
129 Correct 103 ms 158160 KB Output is correct
130 Correct 113 ms 158964 KB Output is correct
131 Correct 107 ms 158404 KB Output is correct
132 Correct 101 ms 158116 KB Output is correct
133 Correct 442 ms 173292 KB Output is correct
134 Correct 337 ms 171096 KB Output is correct
135 Correct 255 ms 170340 KB Output is correct
136 Correct 145 ms 167956 KB Output is correct
137 Correct 446 ms 173356 KB Output is correct
138 Correct 357 ms 171016 KB Output is correct
139 Correct 275 ms 169984 KB Output is correct
140 Correct 204 ms 169140 KB Output is correct
141 Correct 493 ms 174944 KB Output is correct
142 Correct 440 ms 174256 KB Output is correct
143 Correct 407 ms 174088 KB Output is correct
144 Correct 412 ms 174012 KB Output is correct
145 Correct 459 ms 175804 KB Output is correct
146 Correct 466 ms 175748 KB Output is correct
147 Correct 480 ms 175724 KB Output is correct
148 Correct 461 ms 175672 KB Output is correct
149 Correct 438 ms 173564 KB Output is correct
150 Correct 342 ms 171292 KB Output is correct
151 Correct 259 ms 170276 KB Output is correct
152 Correct 144 ms 168196 KB Output is correct
153 Correct 424 ms 173392 KB Output is correct
154 Correct 348 ms 171188 KB Output is correct
155 Correct 261 ms 170280 KB Output is correct
156 Correct 210 ms 169332 KB Output is correct
157 Correct 469 ms 175196 KB Output is correct
158 Correct 439 ms 174576 KB Output is correct
159 Correct 412 ms 174388 KB Output is correct
160 Correct 489 ms 174240 KB Output is correct
161 Correct 464 ms 175728 KB Output is correct
162 Correct 451 ms 175764 KB Output is correct
163 Correct 452 ms 175884 KB Output is correct
164 Correct 449 ms 175980 KB Output is correct
165 Correct 128 ms 167404 KB Output is correct
166 Correct 133 ms 167372 KB Output is correct
167 Correct 129 ms 167448 KB Output is correct
168 Correct 133 ms 167364 KB Output is correct
169 Correct 214 ms 169272 KB Output is correct
170 Correct 186 ms 168756 KB Output is correct
171 Correct 176 ms 168636 KB Output is correct
172 Correct 139 ms 167660 KB Output is correct
173 Correct 507 ms 173436 KB Output is correct
174 Correct 332 ms 170792 KB Output is correct
175 Correct 263 ms 169780 KB Output is correct
176 Correct 139 ms 167620 KB Output is correct
177 Correct 422 ms 172896 KB Output is correct
178 Correct 327 ms 170384 KB Output is correct
179 Correct 238 ms 169448 KB Output is correct
180 Correct 144 ms 167760 KB Output is correct
181 Correct 164 ms 168092 KB Output is correct
182 Correct 220 ms 168060 KB Output is correct
183 Correct 177 ms 167744 KB Output is correct
184 Correct 209 ms 167740 KB Output is correct
185 Correct 169 ms 168040 KB Output is correct
186 Correct 213 ms 168012 KB Output is correct
187 Correct 162 ms 167788 KB Output is correct
188 Correct 210 ms 167752 KB Output is correct
189 Correct 166 ms 168088 KB Output is correct
190 Correct 209 ms 168104 KB Output is correct
191 Correct 262 ms 175700 KB Output is correct
192 Correct 282 ms 175604 KB Output is correct
193 Correct 753 ms 209040 KB Output is correct
194 Correct 768 ms 208992 KB Output is correct
195 Correct 1413 ms 254556 KB Output is correct
196 Correct 1383 ms 254660 KB Output is correct
197 Correct 1628 ms 273428 KB Output is correct
198 Correct 1674 ms 273308 KB Output is correct
199 Correct 2285 ms 215884 KB Output is correct
200 Correct 1551 ms 209816 KB Output is correct
201 Correct 1488 ms 208644 KB Output is correct
202 Correct 2602 ms 220256 KB Output is correct
203 Correct 1563 ms 209980 KB Output is correct
204 Correct 1477 ms 208832 KB Output is correct
205 Correct 2765 ms 221936 KB Output is correct
206 Correct 1562 ms 209944 KB Output is correct
207 Correct 1524 ms 208768 KB Output is correct
208 Correct 1059 ms 199872 KB Output is correct
209 Correct 1020 ms 199784 KB Output is correct
210 Correct 1076 ms 199872 KB Output is correct
211 Correct 1137 ms 200120 KB Output is correct
212 Correct 1119 ms 199920 KB Output is correct
213 Correct 6236 ms 251488 KB Output is correct
214 Correct 4622 ms 230116 KB Output is correct
215 Correct 3349 ms 221660 KB Output is correct
216 Correct 1202 ms 207136 KB Output is correct
217 Correct 5581 ms 252616 KB Output is correct
218 Correct 4318 ms 232056 KB Output is correct
219 Correct 2982 ms 223212 KB Output is correct
220 Correct 1516 ms 211240 KB Output is correct
221 Correct 5558 ms 268188 KB Output is correct
222 Correct 5039 ms 262344 KB Output is correct
223 Correct 4962 ms 260520 KB Output is correct
224 Correct 4869 ms 260172 KB Output is correct
225 Correct 5507 ms 274364 KB Output is correct
226 Correct 5627 ms 274344 KB Output is correct
227 Correct 5560 ms 274444 KB Output is correct
228 Correct 5466 ms 274420 KB Output is correct
229 Correct 5415 ms 251504 KB Output is correct
230 Correct 4242 ms 229888 KB Output is correct
231 Correct 2924 ms 221764 KB Output is correct
232 Correct 1135 ms 207040 KB Output is correct
233 Correct 5305 ms 252504 KB Output is correct
234 Correct 4205 ms 231660 KB Output is correct
235 Correct 3192 ms 223404 KB Output is correct
236 Correct 1636 ms 212204 KB Output is correct
237 Correct 5498 ms 268064 KB Output is correct
238 Correct 5250 ms 262048 KB Output is correct
239 Correct 5090 ms 260288 KB Output is correct
240 Correct 5010 ms 267468 KB Output is correct
241 Correct 6077 ms 281440 KB Output is correct
242 Correct 6341 ms 281520 KB Output is correct
243 Correct 6109 ms 281564 KB Output is correct
244 Correct 6325 ms 281236 KB Output is correct
245 Correct 649 ms 199496 KB Output is correct
246 Correct 656 ms 199568 KB Output is correct
247 Correct 666 ms 199536 KB Output is correct
248 Correct 638 ms 199520 KB Output is correct
249 Correct 1541 ms 216800 KB Output is correct
250 Correct 1648 ms 218264 KB Output is correct
251 Correct 1749 ms 219112 KB Output is correct
252 Correct 949 ms 208324 KB Output is correct
253 Correct 5383 ms 261128 KB Output is correct
254 Correct 3894 ms 235920 KB Output is correct
255 Correct 2748 ms 226120 KB Output is correct
256 Correct 1020 ms 209308 KB Output is correct
257 Correct 5337 ms 254512 KB Output is correct
258 Correct 4089 ms 231164 KB Output is correct
259 Correct 3015 ms 222104 KB Output is correct
260 Correct 1029 ms 208124 KB Output is correct
261 Correct 1097 ms 239736 KB Output is correct
262 Correct 2699 ms 239556 KB Output is correct
263 Correct 958 ms 234560 KB Output is correct
264 Correct 2459 ms 234652 KB Output is correct
265 Correct 1093 ms 239648 KB Output is correct
266 Correct 2598 ms 239560 KB Output is correct
267 Correct 982 ms 234644 KB Output is correct
268 Correct 2370 ms 234572 KB Output is correct
269 Correct 1636 ms 280928 KB Output is correct
270 Correct 1667 ms 280764 KB Output is correct
271 Correct 2608 ms 223488 KB Output is correct
272 Correct 1585 ms 215280 KB Output is correct
273 Correct 2783 ms 228224 KB Output is correct
274 Correct 1566 ms 215816 KB Output is correct
275 Correct 217 ms 174712 KB Output is correct