Submission #1004512

---

Source Code Expand

#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
     
#define pb emplace_back
#define fi first
#define se second
     
using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+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); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ ll x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

int n;
int a[100010];
string s;

int lens[100010];
set<int> so, sz;
priority_queue<pi,vpi,greater<pi> > qo, qz;

void add( int p , int l , bool f ){
  lens[p] = l;
  if( f ){
    so.insert( p );
    qo.emplace( l , p );
  } else {
    sz.insert( p );
    qz.emplace( l , p );
  }
}

bool check( int x ){
  while( !qo.empty() ){
    qo.pop();
  }
  while( !qo.empty() ){
    qz.pop();
  }
  so.clear();
  sz.clear();
  REP( i , n ){
    lens[i] = -1;
  }
  bool cur = a[0] >= x;
  int prv = 0;
  FOR( i , 1 , n ){
    if( cur != ( a[i] >= x ) ){
      add( prv , i-prv , cur );
      prv = i;
      cur = a[i] >= x;
    }
  }
  add( prv , n-prv , cur );
  int one = 0;
  int zero = 0;
  YYS( w , s ){
    if( w == 'M' ){
      one++;
    } else if( 'm' ){
      zero++;
    } else {
      assert( false );
    }
    // cout << w << endl;
    while( !qz.empty() and qz.top().fi + zero - one <= 0 ){
      assert( qz.top().fi + zero - one == 0 );
      int len = qz.top().fi;
      int p = qz.top().se;
      qz.pop();
      if( lens[p] != len ){
	continue;
      }
      // cout << "Z " << len << " " << p << endl;
      sz.erase( sz.find( p ) );
      auto r = so.upper_bound( p );
      if( r == so.begin() or r == so.end() ){
	continue;
      }
      auto l = r;
      l--;
      lens[*l] = lens[*r] + lens[*l] + one - zero;
      lens[*r] = -1;
      so.erase( r );
      qo.emplace( lens[*l] , *l );
    }
    while( !qo.empty() and qo.top().fi + one - zero <= 0 ){
      assert( qo.top().fi + one - zero == 0 );
      int len = qo.top().fi;
      int p = qo.top().se;
      qo.pop();
      if( lens[p] != len ){
	continue;
      }
      // cout << "O " << len << " " << p << endl;
      so.erase( so.find( p ) );
      auto r = sz.upper_bound( p );
      if( r == sz.begin() or r == sz.end() ){
	continue;
      }
      auto l = r;
      l--;
      lens[*l] = lens[*r] + lens[*l] + zero - one;
      lens[*r] = -1;
      sz.erase( r );
      qz.emplace( lens[*l] , *l );
    }
  }

  int ans = 0;
  YYS( w , sz ){
    int l = w - zero;
    int r = w + lens[w] - one;
    if( l <= 0 and 0 < r ){
      assert( ans == 0 );
      // cout << l << " " << r << endl;
      ans = 1;
    }
  }

  YYS( w , so ){
    int l = w - one;
    int r = w + lens[w] - zero;
    if( l <= 0 and 0 < r ){
      // cout << l << " " << r << endl;
      assert( ans == 0 );
      ans = 2;
    }
  }

  assert( ans != 0 );
  if( ans == 1 ){
    return false;
  } else {
    return true;
  }
}

int main(){

  n = in();
  REP( i , n ){
    a[i] = in();
  }
  s = stin();

  // check( 12 );

  /*
  REP( j , n ){
    cout << ( a[j] >= 12 ) << " ";
  }
  cout << endl;
  
  int b[20];
  REP( i , n-1 ){
    if( s[i] == 'm' ){
      REP( j , n-i-1 ){
	b[j] = min( a[j] , a[j+1] );
      }
    } else {
      REP( j , n-i-1 ){
	b[j] = max( a[j] , a[j+1] );
      }
    }
    REP( j , n-i-1 ){
      a[j] = b[j];
      cout << ( a[j] >= 12 ) << " ";
    }
    cout << endl;
  }
  */
  
  int lb = 0, ub = n + 1;
  while( ub - lb > 1 ){
    int md = ( lb + ub ) / 2;
    if( check( md ) ){
      lb = md;
    } else {
      ub = md;
    }
  }

  cout << lb << endl;
  
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll in()’:
./Main.cpp:44:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll in(){ ll x; scanf( "%lld" , &x ); return x; }
                                    ^
./Main.cpp: In function ‘std::string stin()’:
./Main.cpp:45:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }
                                                                  ^

Judge Result