oj.uz

Submission #835650

# Submission time Handle Problem Language Result Execution time Memory
835650 2023-08-23T17:13:03 Z lollipop Radio Towers (IOI22_towers) C++17
100 / 100
 1272 ms 27740 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define ll long long
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 1000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
//mt19937 R(time(0));
map < string , int > ma , ma1 ;

#include "towers.h"


// first type of segment tree 
struct stu{
	int mn , mx , val , val1 , pos ; 
};
stu node[ 4 * N ] , xx ;
int a[ N ] , n ; 

stu combine( stu a , stu b ){
	stu c ; c.mx = max( a.mx , b.mx ) ;
	c.mn = min( a.mn , b.mn ) ;
	c.val = max( { a.val , b.val , b.mx - a.mn } ) ;
	c.val1 = max( { a.val1 , b.val1 , a.mx - b.mn } ) ;
	if( a.mn < b.mn ) c.pos = a.pos ;
	else c.pos = b.pos ; 
	return c ; 
}
void build( int v , int vl , int vr ){
	if( vl == vr ){
		node[ v ] = { a[ vl ] , a[ vl ] , 0 , 0 , vl } ;
		return ;
	}
	int vm = ( vl + vr ) / 2 ;
	build( v + v , vl , vm ) ;
	build( v + v + 1 , vm + 1 , vr ) ;
	node[ v ] = combine( node[ v + v ] , node[ v + v + 1 ] ) ;
}
stu get_df( int v , int vl , int vr , int l , int r ){
	if( l > r ) return xx ;
	if( vl == l && vr == r ) return node[ v ] ;
	int vm = ( vl + vr ) / 2 ;
	stu a , b ;
	a = get_df( v + v , vl , vm , l , min( r , vm ) ) ;
	b = get_df( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r ) ;
	return combine( a , b ) ;  
}
int get_clos( int v , int vl , int vr , int l , int r , int val , int nd ){
	if( l > r ) return -1 ;	
	if( node[ v ].mx < val ) return -1 ;
	if( vl == vr ) return vl ; 
	int vm = ( vl + vr ) / 2 ; 
	// nd == -1 --> marcxnidan
	// nd == 1 --> marjvnidan
	if( nd == -1 ){
		int x = -1 ;
		if( node[ v + v + 1 ].mx >= val ){
			x = get_clos( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r , val , nd ) ;
		}
		if( x == -1 ) 
		 x = get_clos( v + v , vl , vm , l , min( r , vm ) , val , nd ) ; 
		return x ; 
	}
	else{
		int x = -1 ;
		if( node[ v + v ].mx >= val ){
			x = get_clos( v + v , vl , vm , l , min( r , vm ) , val , nd ) ; 
		}
		if( x == -1 ) 
		 x = get_clos( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r , val , nd ) ; 
		return x ; 		
	}
}

// now you need a new persistent_seg_tree with decreasing Diff 
// anu ginda jami da yvelaze marcx_yvelaze_marjv

int clos_l[ N ] , clos_r[ N ] ; 
map < int , int > lst ; 

int cc = 2 ;
pair < int , int > sn[ 20 * N ] ;
int jm[ 20 * N ] ;

void build_ot( int v , int vl , int vr ){
	if( vl == vr ){
		jm[ v ] = 0 ; return ;
	}
	int vm = ( vl + vr ) / 2 ;
	sn[ v ].f = cc ; cc ++ ; 
	build_ot( sn[ v ].f , vl , vm ) ;
	sn[ v ].s = cc ; cc ++ ;
	build_ot( sn[ v ].s , vm + 1 , vr ) ;
	jm[ v ] = 0 ; 
	return ;
}
void update_ot( int v , int pp , int vl , int vr , int pos ){
	if( vl == vr ){
		jm[ v ] = 1 ; 
		return ;  
	}
	int vm = ( vl + vr ) / 2 ;
	if( vm >= pos ){
	   sn[ v ].f = cc ; cc ++ ; 
	   sn[ v ].s = sn[ pp ].s ;
	   update_ot( sn[ v ].f , sn[ pp ].f , vl , vm , pos ) ; 
	}
	else{
	   sn[ v ].s = cc ; cc ++ ; 
	   sn[ v ].f = sn[ pp ].f ;
	   update_ot( sn[ v ].s , sn[ pp ].s , vm + 1 , vr , pos ) ; 		
	}
	jm[ v ] = jm[ sn[ v ].f ] + jm[ sn[ v ].s ] ;
}

int sum( int v , int vl , int vr , int l , int r ){
	if( l > r ) return 0 ;
	if( vl == l && vr == r ) return jm[ v ] ;
	int vm = ( vl + vr ) / 2 ;
	int a , b ;
	a = sum( sn[ v ].f , vl , vm , l , min( r , vm ) ) ;
	b = sum( sn[ v ].s , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
	return ( a + b ) ; 
}
int get_ert( int v , int vl , int vr , int l , int r , int tp ){
	if( l > r ) return -1 ; 
	if( jm[ v ] == 0 ) return -1 ;	
	if( vl == vr ) return vl ;
	int vm = ( vl + vr ) / 2 ;
	// -1 --> marcxena
	// 1 --> marjvena
	if( tp == -1 ){
		int x = -1 ;
		if( jm[ sn[ v ].f ] != 0 ){
			x = get_ert( sn[ v ].f , vl , vm , l , min( r , vm ) , tp ) ; 
		}
		if( x == -1 ) x = get_ert( sn[ v ].s , vm + 1 , vr , max( l , vm + 1 ) , r , tp ) ;
		return x ; 
	}
	else{
		int x = -1 ;
		if( jm[ sn[ v ].s ] != 0 ){
			x = get_ert( sn[ v ].s , vm + 1 , vr , max( l , vm + 1 ) , r , tp ) ;
		}
		if( x == -1 ) x = get_ert( sn[ v ].f , vl , vm , l , min( r , vm ) , tp ) ; 
		return x ; 		
	}
}
set < pair < int , int > > se ; 
stack < int > st ; set < int > sis ; 
void init(int N, std::vector<int> H){
    n = N ; FOR( i , N ) a[ i + 1 ] = H[ i ] ;
    // if this works make it into segment tree ?
    xx.mn = 1e9 + 1 ; xx.mx = -1e9 - 1 ; xx.val = 0 ; xx.val1 = 0 ; xx.pos = -1 ;
    build( 1 , 1 , n ) ;
    build_ot( 1 , 1 , n ) ;
	// left to right  
    for( int j = 1 ; j <= n ; j ++ ){
    	while( true ){
    		if( st.size() == 0 ) break ;
    		if( a[ st.top() ] > a[ j ] ){
    			st.pop() ; 
			} else break ; 
		}
		if( st.size() == 0 ){
			clos_l[ j ] = 0 ; 
		} else clos_l[ j ] = st.top() ; 
		st.push( j ) ; 
	}
    // right to left 
    while( st.size() > 0 ) st.pop() ;
    for( int j = n ; j >= 1 ; j -- ){
    	while( true ){
    		if( st.size() == 0 ) break ;
    		if( a[ st.top() ] > a[ j ] ){
    			st.pop() ; 
			} else break ; 
		}
		if( st.size() == 0 ){
			clos_r[ j ] = n + 1 ; 
		} else clos_r[ j ] = st.top() ; 
		st.push( j ) ; 
	}    
	vector < pair < int , int > > v ;
	for( int j = 1 ; j <= n ; j ++ ){
		if( clos_l[ j ] == j - 1 || clos_r[ j ] == j + 1 ) continue ;
		stu bb = get_df( 1 , 1 , n , clos_l[ j ] + 1 , j ) ;
		stu aa = get_df( 1 , 1 , n , j , clos_r[ j ] - 1 ) ;
		bb.mx = min( bb.mx , aa.mx ) ; 
		int af = bb.mx - a[ j ] ;
		v.pb( { af , j } ) ; 
		//cout << af << " " << j << endl ;
	}
	sort( v.begin() , v.end() ) ; 	
    // now slowly create persistent seg tree
    int bef = 1 ;
    for( int j = v.size() - 1 ; j >= 0 ; j -- ){
    	pair < int , int > p ; 
    	p = v[ j ] ; 
    	int cur = cc ; cc ++ ;
    	lst[ p.f ] = cur ; 
    	update_ot( cur , bef , 1 , n , p.s ) ;
    	bef = cur ; 
    	sis.insert( p.f ) ; 
	}
    for( auto x : sis ){
    	se.insert( { x , lst[ x ] } ) ; 
	}   
}

int check( int l , int r , int pos , int tp , int d ){
	// -1 --> marcxnidan
	// 1 --> marjvnidan
	if( tp == -1 ){
		int xix = get_clos( 1 , 1 , n , l , pos , a[ pos ] + 1 , -1 ) ;
		if( xix == -1 ) return 0 ;
		stu ch = get_df( 1 , 1 , n , l , xix ) ; 
		if( ch.val < d ) return 0 ;
		return 1 ; 
	}
	if( tp == 1 ){
		int xix = get_clos( 1 , 1 , n , pos , r , a[ pos ] + 1 , 1 ) ;
		if( xix == -1 ) return 0 ;
		stu ch = get_df( 1 , 1 , n , xix , r ) ; 
		if( ch.val1 < d ) return 0 ;
		return 1 ; 
	}	
}
int max_towers(int L, int R, int D){
   L ++ ; R ++ ;    
   pair < int , int > p ; p.s = 1 ;
   if( se.size() != 0 )
   if( (*(--se.end() )).f >= D ) 
   p = *(se.lower_bound( { D , 0 } ) ) ; 
   int root = p.s ; 
   // now calculate the answerr 
   int ans = sum( root , 1 , n , L , R ) ;
  // if( L == 1 && R == n ) return ans ;
   if( ans == 0 ){
   	 stu cur ; cur = get_df( 1 , 1 , n , L , R ) ;
   	 int pos = cur.pos ; 
   	 if( check( L , R , pos , -1 , D ) == 1 || check( L , R , pos , 1 , D ) == 1 ) return 2 ;
   	 return 1 ;
   }
   // else we have left_right
   int lf = get_ert( root , 1 , n , L , R , -1 ) ;
   int rg = get_ert( root , 1 , n , L , R , 1 ) ;
  // cout << lf << " " << rg << endl ;
   if( lf != -1 )
   ans = ans + check( L , R , lf , -1 , D ) ;
   if( rg != -1 )
   ans = ans + check( L , R , rg , 1 , D ) ;
   return ans ;
   
}


// int main() {
//   int N, Q;
//   assert(2 == scanf("%d %d", &N, &Q));
//   std::vector<int> H(N);
//   for (int i = 0; i < N; ++i) {
//     assert(1 == scanf("%d", &H[i]));
//   }
//   init(N, H);
//
//   for (int i = 0; i < Q; ++i) {
//     int L, R, D;
//     assert(3 == scanf("%d %d %d", &L, &R, &D));
//     printf("%d\n", max_towers(L, R, D));
//   }
//   return 0;
// }

Compilation message

towers.cpp: In function 'int check(int, int, int, int, int)':
towers.cpp:252:1: warning: control reaches end of non-void function [-Wreturn-type]
  252 | }
      | ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 5584 KB Output is correct
2 Correct 921 ms 10064 KB Output is correct
3 Correct 1096 ms 10064 KB Output is correct
4 Correct 732 ms 10192 KB Output is correct
5 Correct 933 ms 10192 KB Output is correct
6 Correct 918 ms 10156 KB Output is correct
7 Correct 960 ms 10160 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 1 ms 720 KB Output is correct
7 Correct 2 ms 720 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 336 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 720 KB Output is correct
17 Correct 2 ms 720 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 592 KB Output is correct
21 Correct 2 ms 720 KB Output is correct
22 Correct 2 ms 720 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 464 KB Output is correct
26 Correct 2 ms 632 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 2 ms 720 KB Output is correct
29 Correct 2 ms 720 KB Output is correct
30 Correct 2 ms 720 KB Output is correct
31 Correct 2 ms 720 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 464 KB Output is correct
35 Correct 1 ms 464 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 1 ms 720 KB Output is correct
7 Correct 2 ms 720 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 336 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 720 KB Output is correct
17 Correct 2 ms 720 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 592 KB Output is correct
21 Correct 2 ms 720 KB Output is correct
22 Correct 2 ms 720 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 464 KB Output is correct
26 Correct 2 ms 632 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 2 ms 720 KB Output is correct
29 Correct 2 ms 720 KB Output is correct
30 Correct 2 ms 720 KB Output is correct
31 Correct 2 ms 720 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 464 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 37 ms 13124 KB Output is correct
37 Correct 60 ms 21632 KB Output is correct
38 Correct 69 ms 21628 KB Output is correct
39 Correct 87 ms 27556 KB Output is correct
40 Correct 83 ms 27508 KB Output is correct
41 Correct 82 ms 27504 KB Output is correct
42 Correct 90 ms 27508 KB Output is correct
43 Correct 16 ms 10188 KB Output is correct
44 Correct 13 ms 10180 KB Output is correct
45 Correct 14 ms 10060 KB Output is correct
46 Correct 13 ms 10012 KB Output is correct
47 Correct 64 ms 21548 KB Output is correct
48 Correct 82 ms 27480 KB Output is correct
49 Correct 84 ms 27596 KB Output is correct
50 Correct 14 ms 10192 KB Output is correct
51 Correct 14 ms 10064 KB Output is correct
52 Correct 58 ms 21624 KB Output is correct
53 Correct 80 ms 27520 KB Output is correct
54 Correct 90 ms 27624 KB Output is correct
55 Correct 13 ms 10192 KB Output is correct
56 Correct 14 ms 9936 KB Output is correct
57 Correct 60 ms 20964 KB Output is correct
58 Correct 65 ms 21544 KB Output is correct
59 Correct 68 ms 21704 KB Output is correct
60 Correct 80 ms 27568 KB Output is correct
61 Correct 80 ms 27508 KB Output is correct
62 Correct 79 ms 27548 KB Output is correct
63 Correct 95 ms 27740 KB Output is correct
64 Correct 14 ms 10192 KB Output is correct
65 Correct 14 ms 10192 KB Output is correct
66 Correct 13 ms 9932 KB Output is correct
67 Correct 13 ms 10064 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 21436 KB Output is correct
2 Correct 843 ms 21576 KB Output is correct
3 Correct 870 ms 21548 KB Output is correct
4 Correct 996 ms 27544 KB Output is correct
5 Correct 964 ms 27564 KB Output is correct
6 Correct 955 ms 27488 KB Output is correct
7 Correct 953 ms 27504 KB Output is correct
8 Correct 824 ms 10184 KB Output is correct
9 Correct 648 ms 10116 KB Output is correct
10 Correct 788 ms 10068 KB Output is correct
11 Correct 772 ms 10064 KB Output is correct
12 Correct 859 ms 10192 KB Output is correct
13 Correct 828 ms 10316 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 1 ms 464 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 63 ms 21648 KB Output is correct
18 Correct 81 ms 27508 KB Output is correct
19 Correct 85 ms 27488 KB Output is correct
20 Correct 14 ms 10192 KB Output is correct
21 Correct 14 ms 10064 KB Output is correct
22 Correct 65 ms 21568 KB Output is correct
23 Correct 85 ms 27480 KB Output is correct
24 Correct 100 ms 27668 KB Output is correct
25 Correct 13 ms 10184 KB Output is correct
26 Correct 20 ms 9928 KB Output is correct
27 Correct 1 ms 592 KB Output is correct
28 Correct 2 ms 720 KB Output is correct
29 Correct 1 ms 720 KB Output is correct
30 Correct 1 ms 464 KB Output is correct
31 Correct 1 ms 464 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 720 KB Output is correct
34 Correct 1 ms 720 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 1 ms 464 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 5200 KB Output is correct
2 Correct 718 ms 21608 KB Output is correct
3 Correct 798 ms 21568 KB Output is correct
4 Correct 835 ms 27576 KB Output is correct
5 Correct 793 ms 27536 KB Output is correct
6 Correct 880 ms 27496 KB Output is correct
7 Correct 943 ms 27524 KB Output is correct
8 Correct 713 ms 10184 KB Output is correct
9 Correct 517 ms 10192 KB Output is correct
10 Correct 708 ms 10060 KB Output is correct
11 Correct 591 ms 10064 KB Output is correct
12 Correct 68 ms 21556 KB Output is correct
13 Correct 82 ms 27548 KB Output is correct
14 Correct 81 ms 27552 KB Output is correct
15 Correct 13 ms 10192 KB Output is correct
16 Correct 13 ms 9972 KB Output is correct
17 Correct 57 ms 21028 KB Output is correct
18 Correct 60 ms 21616 KB Output is correct
19 Correct 77 ms 21784 KB Output is correct
20 Correct 79 ms 27488 KB Output is correct
21 Correct 81 ms 27492 KB Output is correct
22 Correct 77 ms 27484 KB Output is correct
23 Correct 83 ms 27544 KB Output is correct
24 Correct 13 ms 10192 KB Output is correct
25 Correct 13 ms 10176 KB Output is correct
26 Correct 18 ms 10192 KB Output is correct
27 Correct 13 ms 10056 KB Output is correct
28 Correct 1 ms 592 KB Output is correct
29 Correct 1 ms 720 KB Output is correct
30 Correct 1 ms 720 KB Output is correct
31 Correct 1 ms 464 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 592 KB Output is correct
35 Correct 1 ms 592 KB Output is correct
36 Correct 1 ms 720 KB Output is correct
37 Correct 2 ms 720 KB Output is correct
38 Correct 2 ms 736 KB Output is correct
39 Correct 2 ms 720 KB Output is correct
40 Correct 1 ms 464 KB Output is correct
41 Correct 1 ms 464 KB Output is correct
42 Correct 1 ms 512 KB Output is correct
43 Correct 1 ms 464 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 1 ms 720 KB Output is correct
7 Correct 2 ms 720 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 336 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 720 KB Output is correct
17 Correct 2 ms 720 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 592 KB Output is correct
21 Correct 2 ms 720 KB Output is correct
22 Correct 2 ms 720 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 464 KB Output is correct
26 Correct 2 ms 632 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 2 ms 720 KB Output is correct
29 Correct 2 ms 720 KB Output is correct
30 Correct 2 ms 720 KB Output is correct
31 Correct 2 ms 720 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 464 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 37 ms 13124 KB Output is correct
37 Correct 60 ms 21632 KB Output is correct
38 Correct 69 ms 21628 KB Output is correct
39 Correct 87 ms 27556 KB Output is correct
40 Correct 83 ms 27508 KB Output is correct
41 Correct 82 ms 27504 KB Output is correct
42 Correct 90 ms 27508 KB Output is correct
43 Correct 16 ms 10188 KB Output is correct
44 Correct 13 ms 10180 KB Output is correct
45 Correct 14 ms 10060 KB Output is correct
46 Correct 13 ms 10012 KB Output is correct
47 Correct 64 ms 21548 KB Output is correct
48 Correct 82 ms 27480 KB Output is correct
49 Correct 84 ms 27596 KB Output is correct
50 Correct 14 ms 10192 KB Output is correct
51 Correct 14 ms 10064 KB Output is correct
52 Correct 58 ms 21624 KB Output is correct
53 Correct 80 ms 27520 KB Output is correct
54 Correct 90 ms 27624 KB Output is correct
55 Correct 13 ms 10192 KB Output is correct
56 Correct 14 ms 9936 KB Output is correct
57 Correct 60 ms 20964 KB Output is correct
58 Correct 65 ms 21544 KB Output is correct
59 Correct 68 ms 21704 KB Output is correct
60 Correct 80 ms 27568 KB Output is correct
61 Correct 80 ms 27508 KB Output is correct
62 Correct 79 ms 27548 KB Output is correct
63 Correct 95 ms 27740 KB Output is correct
64 Correct 14 ms 10192 KB Output is correct
65 Correct 14 ms 10192 KB Output is correct
66 Correct 13 ms 9932 KB Output is correct
67 Correct 13 ms 10064 KB Output is correct
68 Correct 718 ms 21436 KB Output is correct
69 Correct 843 ms 21576 KB Output is correct
70 Correct 870 ms 21548 KB Output is correct
71 Correct 996 ms 27544 KB Output is correct
72 Correct 964 ms 27564 KB Output is correct
73 Correct 955 ms 27488 KB Output is correct
74 Correct 953 ms 27504 KB Output is correct
75 Correct 824 ms 10184 KB Output is correct
76 Correct 648 ms 10116 KB Output is correct
77 Correct 788 ms 10068 KB Output is correct
78 Correct 772 ms 10064 KB Output is correct
79 Correct 859 ms 10192 KB Output is correct
80 Correct 828 ms 10316 KB Output is correct
81 Correct 0 ms 336 KB Output is correct
82 Correct 1 ms 464 KB Output is correct
83 Correct 1 ms 464 KB Output is correct
84 Correct 63 ms 21648 KB Output is correct
85 Correct 81 ms 27508 KB Output is correct
86 Correct 85 ms 27488 KB Output is correct
87 Correct 14 ms 10192 KB Output is correct
88 Correct 14 ms 10064 KB Output is correct
89 Correct 65 ms 21568 KB Output is correct
90 Correct 85 ms 27480 KB Output is correct
91 Correct 100 ms 27668 KB Output is correct
92 Correct 13 ms 10184 KB Output is correct
93 Correct 20 ms 9928 KB Output is correct
94 Correct 1 ms 592 KB Output is correct
95 Correct 2 ms 720 KB Output is correct
96 Correct 1 ms 720 KB Output is correct
97 Correct 1 ms 464 KB Output is correct
98 Correct 1 ms 464 KB Output is correct
99 Correct 1 ms 592 KB Output is correct
100 Correct 1 ms 720 KB Output is correct
101 Correct 1 ms 720 KB Output is correct
102 Correct 1 ms 464 KB Output is correct
103 Correct 1 ms 464 KB Output is correct
104 Correct 831 ms 19728 KB Output is correct
105 Correct 905 ms 21664 KB Output is correct
106 Correct 929 ms 21560 KB Output is correct
107 Correct 901 ms 27492 KB Output is correct
108 Correct 1029 ms 27484 KB Output is correct
109 Correct 986 ms 27460 KB Output is correct
110 Correct 1044 ms 27560 KB Output is correct
111 Correct 881 ms 10212 KB Output is correct
112 Correct 1033 ms 10192 KB Output is correct
113 Correct 937 ms 9936 KB Output is correct
114 Correct 861 ms 10052 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 5584 KB Output is correct
2 Correct 921 ms 10064 KB Output is correct
3 Correct 1096 ms 10064 KB Output is correct
4 Correct 732 ms 10192 KB Output is correct
5 Correct 933 ms 10192 KB Output is correct
6 Correct 918 ms 10156 KB Output is correct
7 Correct 960 ms 10160 KB Output is correct
8 Correct 0 ms 208 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 336 KB Output is correct
12 Correct 2 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 2 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 1 ms 720 KB Output is correct
17 Correct 2 ms 720 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 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 2 ms 592 KB Output is correct
26 Correct 2 ms 720 KB Output is correct
27 Correct 2 ms 720 KB Output is correct
28 Correct 1 ms 464 KB Output is correct
29 Correct 1 ms 464 KB Output is correct
30 Correct 1 ms 592 KB Output is correct
31 Correct 2 ms 720 KB Output is correct
32 Correct 2 ms 720 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 464 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 2 ms 632 KB Output is correct
37 Correct 2 ms 592 KB Output is correct
38 Correct 2 ms 720 KB Output is correct
39 Correct 2 ms 720 KB Output is correct
40 Correct 2 ms 720 KB Output is correct
41 Correct 2 ms 720 KB Output is correct
42 Correct 1 ms 464 KB Output is correct
43 Correct 1 ms 464 KB Output is correct
44 Correct 1 ms 464 KB Output is correct
45 Correct 1 ms 464 KB Output is correct
46 Correct 37 ms 13124 KB Output is correct
47 Correct 60 ms 21632 KB Output is correct
48 Correct 69 ms 21628 KB Output is correct
49 Correct 87 ms 27556 KB Output is correct
50 Correct 83 ms 27508 KB Output is correct
51 Correct 82 ms 27504 KB Output is correct
52 Correct 90 ms 27508 KB Output is correct
53 Correct 16 ms 10188 KB Output is correct
54 Correct 13 ms 10180 KB Output is correct
55 Correct 14 ms 10060 KB Output is correct
56 Correct 13 ms 10012 KB Output is correct
57 Correct 64 ms 21548 KB Output is correct
58 Correct 82 ms 27480 KB Output is correct
59 Correct 84 ms 27596 KB Output is correct
60 Correct 14 ms 10192 KB Output is correct
61 Correct 14 ms 10064 KB Output is correct
62 Correct 58 ms 21624 KB Output is correct
63 Correct 80 ms 27520 KB Output is correct
64 Correct 90 ms 27624 KB Output is correct
65 Correct 13 ms 10192 KB Output is correct
66 Correct 14 ms 9936 KB Output is correct
67 Correct 60 ms 20964 KB Output is correct
68 Correct 65 ms 21544 KB Output is correct
69 Correct 68 ms 21704 KB Output is correct
70 Correct 80 ms 27568 KB Output is correct
71 Correct 80 ms 27508 KB Output is correct
72 Correct 79 ms 27548 KB Output is correct
73 Correct 95 ms 27740 KB Output is correct
74 Correct 14 ms 10192 KB Output is correct
75 Correct 14 ms 10192 KB Output is correct
76 Correct 13 ms 9932 KB Output is correct
77 Correct 13 ms 10064 KB Output is correct
78 Correct 718 ms 21436 KB Output is correct
79 Correct 843 ms 21576 KB Output is correct
80 Correct 870 ms 21548 KB Output is correct
81 Correct 996 ms 27544 KB Output is correct
82 Correct 964 ms 27564 KB Output is correct
83 Correct 955 ms 27488 KB Output is correct
84 Correct 953 ms 27504 KB Output is correct
85 Correct 824 ms 10184 KB Output is correct
86 Correct 648 ms 10116 KB Output is correct
87 Correct 788 ms 10068 KB Output is correct
88 Correct 772 ms 10064 KB Output is correct
89 Correct 859 ms 10192 KB Output is correct
90 Correct 828 ms 10316 KB Output is correct
91 Correct 0 ms 336 KB Output is correct
92 Correct 1 ms 464 KB Output is correct
93 Correct 1 ms 464 KB Output is correct
94 Correct 63 ms 21648 KB Output is correct
95 Correct 81 ms 27508 KB Output is correct
96 Correct 85 ms 27488 KB Output is correct
97 Correct 14 ms 10192 KB Output is correct
98 Correct 14 ms 10064 KB Output is correct
99 Correct 65 ms 21568 KB Output is correct
100 Correct 85 ms 27480 KB Output is correct
101 Correct 100 ms 27668 KB Output is correct
102 Correct 13 ms 10184 KB Output is correct
103 Correct 20 ms 9928 KB Output is correct
104 Correct 1 ms 592 KB Output is correct
105 Correct 2 ms 720 KB Output is correct
106 Correct 1 ms 720 KB Output is correct
107 Correct 1 ms 464 KB Output is correct
108 Correct 1 ms 464 KB Output is correct
109 Correct 1 ms 592 KB Output is correct
110 Correct 1 ms 720 KB Output is correct
111 Correct 1 ms 720 KB Output is correct
112 Correct 1 ms 464 KB Output is correct
113 Correct 1 ms 464 KB Output is correct
114 Correct 195 ms 5200 KB Output is correct
115 Correct 718 ms 21608 KB Output is correct
116 Correct 798 ms 21568 KB Output is correct
117 Correct 835 ms 27576 KB Output is correct
118 Correct 793 ms 27536 KB Output is correct
119 Correct 880 ms 27496 KB Output is correct
120 Correct 943 ms 27524 KB Output is correct
121 Correct 713 ms 10184 KB Output is correct
122 Correct 517 ms 10192 KB Output is correct
123 Correct 708 ms 10060 KB Output is correct
124 Correct 591 ms 10064 KB Output is correct
125 Correct 68 ms 21556 KB Output is correct
126 Correct 82 ms 27548 KB Output is correct
127 Correct 81 ms 27552 KB Output is correct
128 Correct 13 ms 10192 KB Output is correct
129 Correct 13 ms 9972 KB Output is correct
130 Correct 57 ms 21028 KB Output is correct
131 Correct 60 ms 21616 KB Output is correct
132 Correct 77 ms 21784 KB Output is correct
133 Correct 79 ms 27488 KB Output is correct
134 Correct 81 ms 27492 KB Output is correct
135 Correct 77 ms 27484 KB Output is correct
136 Correct 83 ms 27544 KB Output is correct
137 Correct 13 ms 10192 KB Output is correct
138 Correct 13 ms 10176 KB Output is correct
139 Correct 18 ms 10192 KB Output is correct
140 Correct 13 ms 10056 KB Output is correct
141 Correct 1 ms 592 KB Output is correct
142 Correct 1 ms 720 KB Output is correct
143 Correct 1 ms 720 KB Output is correct
144 Correct 1 ms 464 KB Output is correct
145 Correct 1 ms 464 KB Output is correct
146 Correct 1 ms 464 KB Output is correct
147 Correct 1 ms 592 KB Output is correct
148 Correct 1 ms 592 KB Output is correct
149 Correct 1 ms 720 KB Output is correct
150 Correct 2 ms 720 KB Output is correct
151 Correct 2 ms 736 KB Output is correct
152 Correct 2 ms 720 KB Output is correct
153 Correct 1 ms 464 KB Output is correct
154 Correct 1 ms 464 KB Output is correct
155 Correct 1 ms 512 KB Output is correct
156 Correct 1 ms 464 KB Output is correct
157 Correct 831 ms 19728 KB Output is correct
158 Correct 905 ms 21664 KB Output is correct
159 Correct 929 ms 21560 KB Output is correct
160 Correct 901 ms 27492 KB Output is correct
161 Correct 1029 ms 27484 KB Output is correct
162 Correct 986 ms 27460 KB Output is correct
163 Correct 1044 ms 27560 KB Output is correct
164 Correct 881 ms 10212 KB Output is correct
165 Correct 1033 ms 10192 KB Output is correct
166 Correct 937 ms 9936 KB Output is correct
167 Correct 861 ms 10052 KB Output is correct
168 Correct 0 ms 336 KB Output is correct
169 Correct 705 ms 8208 KB Output is correct
170 Correct 1182 ms 21556 KB Output is correct
171 Correct 1257 ms 21568 KB Output is correct
172 Correct 1143 ms 27520 KB Output is correct
173 Correct 1235 ms 27468 KB Output is correct
174 Correct 1244 ms 27464 KB Output is correct
175 Correct 1272 ms 27604 KB Output is correct
176 Correct 826 ms 10192 KB Output is correct
177 Correct 847 ms 10064 KB Output is correct
178 Correct 841 ms 10064 KB Output is correct
179 Correct 904 ms 9936 KB Output is correct