ABC260D - Draw Your Cards

考え方

Pythonの苦手な順序付き集合．
順序付集合 - 競プロはじめました

あとはlower_boundを使ってやるだけ．

回答例

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> P(N);
    vector<int> ANS(N + 1, -1);
    vector<int> UNDER(N + 1);
    vector<int> NUM(N + 1, 1);
    for (int i = 0; i < N; i++) {
      cin >> P.at(i);
    }
    set<int> s;
    for (int i = 0; i < N; i++) {
      auto it = s.lower_bound(P.at(i));
      if (it == s.end()) {
        if (K == 1) {
          ANS.at(P.at(i)) = i + 1;
        } else {
          s.insert(P.at(i));
        }
      } else {
        if (NUM.at(*it) + 1 == K) {
		   UNDER.at(P.at(i)) = *it;
          int now = P.at(i);
          while (now > 0) {
            ANS.at(now) = i + 1;
            now = UNDER.at(now);
          }
          s.erase(*it);
        } else {
          NUM.at(P.at(i)) = NUM.at(*it) + 1;
          UNDER.at(P.at(i)) = *it;
          s.erase(*it);
          s.insert(P.at(i));
        }
      }
    }
    for (int i = 1; i < N + 1; i++) {
      cout << ANS.at(i) << endl;
    }
    return 0;
}

はじめ，

    map<int, vector<int>> m;

で，各山札をvectorで管理したらTLEした（一番上のカードが変わるたびにmapのキーを書き換えるためにvectorをコピーしたため）．解説（Editorial - AtCoder Beginner Contest 260）の通り，自分の下のカードと，一番上のカードの属する山の枚数を管理すると通った．