mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #344 (Div. 2) C. Report

解法

まず考察です。最初に r1 個のソートをやったとしても, その後に r2 (> r1) 個のソートを行えば, r1 個のソートはなかったことにしても同じです。つまり, ソートは r1 > r2 > r3 > ... というようにソートを行ったと考えても良いです。

r1 のソートが大きい順だったとすると, r2 のソートを行う段階では, [r2, r1) の範囲の数は 「r1 個以内で大きい順に並べた時の, [r2, r1) の範囲にあった数」に決定します。こんな感じのことが解法のアイデアです。

具体的には, a をソートした際の, 残りの数の左端 (lp), 右端(rp) を持っておきます。で,

  • 直前の操作が「大きい順にソート」だった場合, lp を増やしていきながら数列を確定させる
  • 直前の操作が「小さい順にソート」だった場合, rp を減らしていきながら数列を確定させる

とやれば良いですね。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    // r, order, type
    vector<pair<pii, int> > op(m);
    for (int i = 0; i < m; i++) {
        int type, r;
        cin >> type >> r;
        op[i] = make_pair(pii(r, i), type);
    }
    sort(op.rbegin(), op.rend());
    vector<int> ans(n);
    int now = op[0].first.first;
    for (int i = now; i < n; i++) ans[i] = a[i];
    vector<int> b;
    for (int i = 0; i < now; i++) b.push_back(a[i]);
    sort(b.begin(), b.end());
    int lp = 0, rp = now-1;
    int ptype = op[0].second, order = op[0].first.second;
    for (int i = 1; i < m; i++) {
        int r = op[i].first.first, type = op[i].second;
        if (op[i].first.second < order) continue;
        if (ptype == 1) {
            for (int j = now-1; j >= r; j--) ans[j] = b[rp--];
        } else {
            for (int j = now-1; j >= r; j--) ans[j] = b[lp++];
        }
        now = r, ptype = type, order = op[i].first.second;
    }
    if (ptype == 1) {
        for (int j = now-1; j >= 0; j--) ans[j] = b[rp--];
    } else {
        for (int j = now-1; j >= 0; j--) ans[j] = b[lp++];
    }
    for (int i = 0; i < n; i++) cout << ans[i] << " ";
    cout << endl;
    return 0;
}