結果
問題 | No.2248 max(C)-min(C) |
ユーザー | 👑 p-adic |
提出日時 | 2023-06-02 13:45:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,153 ms / 3,000 ms |
コード長 | 2,687 bytes |
コンパイル時間 | 3,484 ms |
コンパイル使用メモリ | 227,992 KB |
実行使用メモリ | 125,344 KB |
最終ジャッジ日時 | 2023-08-28 02:20:16 |
合計ジャッジ時間 | 38,172 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
12,720 KB |
testcase_01 | AC | 6 ms
12,924 KB |
testcase_02 | AC | 7 ms
12,772 KB |
testcase_03 | AC | 9 ms
13,200 KB |
testcase_04 | AC | 7 ms
13,084 KB |
testcase_05 | AC | 7 ms
12,996 KB |
testcase_06 | AC | 10 ms
13,684 KB |
testcase_07 | AC | 10 ms
13,852 KB |
testcase_08 | AC | 11 ms
13,840 KB |
testcase_09 | AC | 10 ms
13,852 KB |
testcase_10 | AC | 8 ms
13,004 KB |
testcase_11 | AC | 10 ms
14,044 KB |
testcase_12 | AC | 8 ms
13,456 KB |
testcase_13 | AC | 9 ms
13,556 KB |
testcase_14 | AC | 10 ms
13,872 KB |
testcase_15 | AC | 11 ms
13,984 KB |
testcase_16 | AC | 8 ms
13,228 KB |
testcase_17 | AC | 10 ms
13,760 KB |
testcase_18 | AC | 944 ms
110,948 KB |
testcase_19 | AC | 78 ms
25,436 KB |
testcase_20 | AC | 1,105 ms
125,344 KB |
testcase_21 | AC | 1,064 ms
119,544 KB |
testcase_22 | AC | 672 ms
87,216 KB |
testcase_23 | AC | 389 ms
60,688 KB |
testcase_24 | AC | 124 ms
31,648 KB |
testcase_25 | AC | 1,021 ms
114,708 KB |
testcase_26 | AC | 850 ms
103,256 KB |
testcase_27 | AC | 983 ms
113,788 KB |
testcase_28 | AC | 59 ms
22,792 KB |
testcase_29 | AC | 884 ms
106,428 KB |
testcase_30 | AC | 297 ms
50,792 KB |
testcase_31 | AC | 1,107 ms
125,228 KB |
testcase_32 | AC | 141 ms
34,388 KB |
testcase_33 | AC | 254 ms
47,712 KB |
testcase_34 | AC | 1,142 ms
125,212 KB |
testcase_35 | AC | 1,103 ms
125,192 KB |
testcase_36 | AC | 1,109 ms
125,268 KB |
testcase_37 | AC | 500 ms
71,220 KB |
testcase_38 | AC | 1,089 ms
117,632 KB |
testcase_39 | AC | 1,102 ms
117,612 KB |
testcase_40 | AC | 1,153 ms
117,532 KB |
testcase_41 | AC | 933 ms
103,188 KB |
testcase_42 | AC | 1,095 ms
117,560 KB |
testcase_43 | AC | 944 ms
106,108 KB |
testcase_44 | AC | 1,112 ms
117,576 KB |
testcase_45 | AC | 829 ms
95,276 KB |
testcase_46 | AC | 373 ms
57,400 KB |
testcase_47 | AC | 1,149 ms
117,576 KB |
testcase_48 | AC | 381 ms
87,772 KB |
testcase_49 | AC | 1,069 ms
125,236 KB |
testcase_50 | AC | 1,058 ms
125,168 KB |
testcase_51 | AC | 1,076 ms
125,168 KB |
testcase_52 | AC | 1,049 ms
125,164 KB |
testcase_53 | AC | 124 ms
31,516 KB |
ソースコード
#ifdef DEBUG #define _GLIBCXX_DEBUG #define CERR( ANSWER ) cerr << ANSWER << "\n"; #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define CERR( ANSWER ) #endif #include <bits/stdc++.h> using namespace std; using ll = long long; #define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- ) #define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define QUIT return 0 #define COUT( ANSWER ) cout << ( ANSWER ) << "\n" #define RETURN( ANSWER ) COUT( ANSWER ); QUIT int main() { UNTIE; CEXPR( int , bound_N , 200000 ); CIN_ASSERT( N , 1 , bound_N ); CEXPR( int , bound_ABi , 1000000000 ); static set<int> AB[bound_N] = {}; map<int,set<int> > Cmin{}; FOR( i , 0 , N ){ CIN_ASSERT( Ai , 0 , bound_ABi ); assert( Ai % 2 == 0 ); AB[i].insert( Ai ); Cmin[Ai].insert( i ); } int Cmax = 0; FOR( i , 0 , N ){ CIN_ASSERT( Bi , 0 , bound_ABi ); assert( Bi % 2 == 0 ); set<int>& ABi = AB[i]; const int& Ai = *ABi.begin(); int mid = ( Ai + Bi ) / 2; ABi.insert( mid ); Cmin[mid].insert( i ); ABi.insert( Bi ); Cmin[Bi].insert( i ); Ai < Bi ? Cmax < Ai ? Cmax = Ai : Cmax : Cmax < Bi ? Cmax = Bi : Cmax; } int answer = bound_ABi; auto itr_Cmin = Cmin.begin(); while( ! Cmin.empty() ){ int temp = Cmax - itr_Cmin->first; CERR( Cmax << "-" << itr_Cmin->first << "=" << temp ); answer > temp ? answer = temp : answer; FOR_ITR( itr_Cmin->second , itr_i , end_i ){ set<int>& ABi = AB[*itr_i]; if( ABi.size() == 1 ){ RETURN( answer ); } auto itr_ABi = ABi.begin(); itr_ABi = ABi.erase( itr_ABi ); CERR( Cmax << "<" << *itr_ABi << "?" ); Cmax < *itr_ABi ? Cmax = *itr_ABi : Cmax; } itr_Cmin = Cmin.erase( itr_Cmin ); } QUIT; }