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].first まで書き込めば終わる
- dp[idx].second != -1
idx = dp[idx].first
- dp[idx].second == -1 (何も記録されていない)
- 削除
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; }