Codeforces Round #641 (Div. 1) B. Orac and Medians

問題ページ

が2つ連続して並んでいる場合、 に操作を適用すればすべて にできるので の並びをつくれるならば 'yes' となる。また 以上 と並んでいる場合、操作を適用すれば の並びをつくれるのでこの場合も 'yes' となる。

あとは 以上 の数を の隣に持ってくることができるか？の判定を行いたい。先程の場合と同様に考えると 以上 が隣接していれば 以上 を の隣に持ってこれる。ある区間に操作を行ったときに 以上 の数が中央値になるならば、以上 の隣接はつくれる。

あとは 以上 が過半数を占めるような区間が存在しているか？を解ければよい。以上 を+1、未満 を-1に置き換えた数列を考えると、総和が1以上である区間が存在することと同値である。あとは zero-sum range と同じで、累積和を取ったあと、累積minを持ちながら順番に参照していけばよい。

▶ソースコード(クリックで展開)

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
void solve() {  
    ll n, k;  
    cin >> n >> k;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
  
    bool exist = false;  
    REP(i, n) if(a[i] == k) exist = true;  
    if(!exist) {  
        cout << "no\n";  
        return;  
    }  
  
    if(n == 1) {  
        cout << "yes\n";  
        return;  
    }  
  
    vector<ll> b(n);  
    REP(i, n) b[i] = (a[i]>=k ? 1 : -1);  
    vector<ll> rui(b);  
    FOR(i, 1, n) rui[i] += rui[i-1];  
    dump(b);  
    dump(rui);  
  
    ll mi = INF;  
    REP(i, n) {  
        dump(i, rui[i], mi);  
        if(rui[i] - mi > 0) {  
            cout << "yes\n";  
            return;  
        }  
        if(i==0) mi = 0;  
        else chmin(mi, rui[i-1]);  
    }  
    cout << "no\n";  
}  
  
int main(void) {  
    ll t;  
    cin >> t;  
    while(t--) solve();  
  
    return 0;  
}