ferinの競プロ帳

競プロについてのメモ

AOJ 2152 Restrictive Filesystem

問題ページ
Restrictive Filesystem | Aizu Online Judge

考えたこと

  • 10^9の配列確保して1つずつ記録していくのはメモリ的にも計算量的にも不可能なので座圧は必須そう
  • dp[i] = (j, k) (位置iからjまでkが記録されている)としてunordered_mapを使ってメモリを節約することを考える
  • 書き込みと削除と参照について場合分けするとそれぞれのクエリにO(N)で対応できそうでO(N^2)なら通る気持ちになったので実装をする
  • TLEが出てつらい気持ちになりながら†submitデバッグ†をするとバグがわかったので直すと通った

やらかしたバグ
* 必要な更新処理をわすれてた * dp[idx]をみないといけないのにdp[i]を見ていた
* 書き込みで値を更新するときにすでに値が入ってるときは書き込んじゃいけないのに書き込んだ

解法

  • 書き込み
    • dp[idx].second == -1 (何も記録されていない)
      • dp[idx].first まで書き込めば終わる
        必要な分の書き込みする
        dpの値の更新
      • 終わらない
        dp[idx].first まで目一杯書き込む
        idx = dp[idx].first
    • dp[idx].second != -1
      idx = dp[idx].first
  • 削除
    dpを全部なめて dp[idx].second が入力された値だったら -1 に変更
  • 参照
    (参照するindex) >= dp[idx].first になるまで idx = dp[idx].first + 1で更新
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif

unordered_map<int, PII> dp;
signed main(void)
{
  while(true) {
    int n;
    cin >> n;
    if(!n) break;

    dp.clear();
    dp[0] = {INF, -1};

    REP(i, n) {
      char c;
      cin >> c;
      int l, r;
      if(c == 'W') {
        cin >> l >> r;
        int idx = 0, cnt = r;
        while(true) {
          if(dp[idx].second == -1) {
            if(idx + cnt - 1 <= dp[idx].first) {
              if(dp.find(idx+cnt) == dp.end()) dp[idx+cnt] = {dp[idx].first, -1};
              dp[idx] = {idx+cnt-1, l};
              break;
            } else {
              dp[idx].second = l;
              cnt -= dp[idx].first - idx + 1;
            }
          }
          idx = dp[idx].first + 1;
        }
      } else if(c == 'D') {
        cin >> l;
        for(auto& j: dp) if(j.second.second == l) j.second.second = -1;
      } else if(c == 'R') {
        cin >> l;
        int idx = 0;
        while(true) {
          if(dp[idx].first >= l) {
            cout << dp[idx].second << endl;
            break;
          }
          idx = dp[idx].first + 1;
        }
      }
    }
    cout << endl;
  }

  return 0;
}