提出 #493217

ソースコード 拡げる

#include <bits/stdc++.h>

#define FOR(i,a,b) for( int i = (a); i < (int)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

using namespace std;

typedef long long int ll;

const int INF = 1e9;
const ll INFLL = 1e18;
const double EPS = 1e-7;

template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }

int in(){ int a; cin >> a; return a; }

#define fi first
#define se second

typedef pair<int,int> P;
typedef vector<ll> vec;

const int MAX_A = 1000010;

vector<int> ss[MAX_A];
vector<P> v;

int ne[MAX_A];

int main(){

  int n;
  cin >> n;

  REP( i , n )
    v.pb( P( in() , i ) );

  REP( i , n )
    ss[ v[i].fi ].pb( v[i].se );

  REP( i , MAX_A )
    sort( ALL(ss[i]) );

  sort( ALL(v) );

  REP( i , n-1 )
    if( v[i].fi != v[i+1].fi )
      ne[ v[i].fi ] = v[i+1].fi;
  
  int fr = -1;
  int cnt = 0;

  int res = 0;
  REP( i , n ){
    if( fr < v[i].se ){
      fr = v[i].se;
      cnt++;
    } else {
      cnt += ss[v[i].fi].end() - lower_bound( ALL(ss[v[i].fi]) , fr );
      chmax( res , cnt );
      fr = v[i].se;
      cnt = 1;
      cnt += upper_bound( ALL(ss[v[i-1].fi]) , fr ) - ss[v[i-1].fi].begin();
    }

    chmax( res , int( upper_bound( ALL(ss[v[i].fi]) , fr ) - ss[v[i].fi].begin() + ss[ne[v[i].fi]].end() - lower_bound( ALL(ss[ne[v[i].fi]]) , fr ) ) );
    
    chmax( res , cnt );
  }

  

  cout << n - res << endl;
  
  return 0;
}

提出情報

提出日時
問題 G - Gowk's Errand for Master
ユーザ kmc
言語 C++11 (GCC 4.8.1)
得点 1
コード長 1578 Byte
結果 AC
実行時間 397 ms
メモリ 37136 KiB

ジャッジ結果

セット名 All
得点 / 配点 1 / 1
結果
AC × 99
セット名 テストケース
All 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, 064.txt, 065.txt, 066.txt, 067.txt, 068.txt, 069.txt, 070.txt, 071.txt, 072.txt, 073.txt, 074.txt, 075.txt, 076.txt, 077.txt, 078.txt, 079.txt, 080.txt, 081.txt, 082.txt, 083.txt, 084.txt, 085.txt, 086.txt, 087.txt, 088.txt, 089.txt, 090.txt, 091.txt, 092.txt, 093.txt, 094.txt, 095.txt, 096.txt, 097.txt, 098.txt, 099.txt
ケース名 結果 実行時間 メモリ
001.txt AC 72 ms 24224 KiB
002.txt AC 69 ms 24212 KiB
003.txt AC 67 ms 24224 KiB
004.txt AC 67 ms 24228 KiB
005.txt AC 66 ms 24228 KiB
006.txt AC 66 ms 24216 KiB
007.txt AC 67 ms 24220 KiB
008.txt AC 67 ms 24220 KiB
009.txt AC 67 ms 24232 KiB
010.txt AC 67 ms 24228 KiB
011.txt AC 69 ms 24136 KiB
012.txt AC 67 ms 24224 KiB
013.txt AC 66 ms 24224 KiB
014.txt AC 68 ms 24228 KiB
015.txt AC 265 ms 29068 KiB
016.txt AC 270 ms 28444 KiB
017.txt AC 269 ms 28560 KiB
018.txt AC 222 ms 29712 KiB
019.txt AC 299 ms 37136 KiB
020.txt AC 259 ms 28936 KiB
021.txt AC 237 ms 28428 KiB
022.txt AC 341 ms 37068 KiB
023.txt AC 331 ms 28944 KiB
024.txt AC 343 ms 28428 KiB
025.txt AC 87 ms 24988 KiB
026.txt AC 335 ms 37064 KiB
027.txt AC 69 ms 24228 KiB
028.txt AC 68 ms 24232 KiB
029.txt AC 67 ms 24224 KiB
030.txt AC 68 ms 24224 KiB
031.txt AC 355 ms 28820 KiB
032.txt AC 364 ms 28368 KiB
033.txt AC 361 ms 28692 KiB
034.txt AC 357 ms 28428 KiB
035.txt AC 361 ms 28432 KiB
036.txt AC 356 ms 28428 KiB
037.txt AC 350 ms 28432 KiB
038.txt AC 353 ms 28372 KiB
039.txt AC 351 ms 28436 KiB
040.txt AC 351 ms 28684 KiB
041.txt AC 358 ms 29200 KiB
042.txt AC 360 ms 29708 KiB
043.txt AC 366 ms 31240 KiB
044.txt AC 365 ms 32268 KiB
045.txt AC 358 ms 32528 KiB
046.txt AC 356 ms 32520 KiB
047.txt AC 367 ms 32652 KiB
048.txt AC 387 ms 33060 KiB
049.txt AC 368 ms 33172 KiB
050.txt AC 335 ms 31944 KiB
051.txt AC 83 ms 24272 KiB
052.txt AC 121 ms 26524 KiB
053.txt AC 112 ms 24984 KiB
054.txt AC 305 ms 28432 KiB
055.txt AC 347 ms 29060 KiB
056.txt AC 323 ms 29708 KiB
057.txt AC 344 ms 29700 KiB
058.txt AC 349 ms 28556 KiB
059.txt AC 357 ms 29068 KiB
060.txt AC 350 ms 29576 KiB
061.txt AC 310 ms 28556 KiB
062.txt AC 351 ms 28944 KiB
063.txt AC 349 ms 28536 KiB
064.txt AC 353 ms 29576 KiB
065.txt AC 355 ms 28552 KiB
066.txt AC 352 ms 28424 KiB
067.txt AC 350 ms 29080 KiB
068.txt AC 305 ms 28436 KiB
069.txt AC 334 ms 28556 KiB
070.txt AC 352 ms 28428 KiB
071.txt AC 349 ms 29708 KiB
072.txt AC 355 ms 29068 KiB
073.txt AC 352 ms 28432 KiB
074.txt AC 344 ms 28560 KiB
075.txt AC 358 ms 28440 KiB
076.txt AC 359 ms 28444 KiB
077.txt AC 353 ms 28432 KiB
078.txt AC 355 ms 28436 KiB
079.txt AC 355 ms 28436 KiB
080.txt AC 353 ms 28436 KiB
081.txt AC 340 ms 28436 KiB
082.txt AC 347 ms 28424 KiB
083.txt AC 339 ms 28432 KiB
084.txt AC 349 ms 28392 KiB
085.txt AC 351 ms 28428 KiB
086.txt AC 350 ms 28432 KiB
087.txt AC 341 ms 30864 KiB
088.txt AC 340 ms 30736 KiB
089.txt AC 336 ms 30856 KiB
090.txt AC 335 ms 30716 KiB
091.txt AC 354 ms 30732 KiB
092.txt AC 366 ms 30852 KiB
093.txt AC 318 ms 34060 KiB
094.txt AC 359 ms 33996 KiB
095.txt AC 352 ms 33936 KiB
096.txt AC 354 ms 33936 KiB
097.txt AC 359 ms 33936 KiB
098.txt AC 374 ms 33936 KiB
099.txt AC 397 ms 34064 KiB