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; }