srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

aoj 2152 Restrictive Filesystem

問題

問題概要

W,D,Lの命令が与えられる。Wは書き込む数字とサイズ、Dは削除する数字、Rは読み込む場所を標示するという命令。書き込むは前から貪欲に、開いている部分にサイズ分書き込むこと。

解法

Wできる区間(空き区間)をprioroty_queueで保持することにした。前から順に書き込んでいくために、区間の左橋が一番小さいものの区間に数を追加しなければならないので、priority_queueを使った。実際の書き込みの実装は、queueから取り出した範囲だけで、サイズ分用意できる場合は、残った部分の区間をqueueに戻して、足りない場合はqueueから次の空き区間を取り出すようにしている。また、書き込んだ値と区間はmapで管理している。
Deleteは、mapからどの区間に書き込んだかを調べ、その区間が空になったということだから、それをqueueに突っ込んだ。
Readは、mapに保持されている区間を全部調べている。

ミス

昨夜TLで流れているのを見て解こうと思った。Readの部分はただ前から順に調べていくだけだとTLEするかなと思ったけど、大丈夫だった。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;

int main(void){
    while(1){
        int n; cin >> n;
        if(n == 0) break;
        priority_queue<pint, vector<pint>, greater<pint> > q;
        q.push(make_pair(0, INF));
        map<int, vpint> m;
        rep(i, n){
            char c; cin >> c;
            if(c == 'W'){
                int num, size; cin >> num >> size;
                while(size > 0){
                    int l = q.top().fi, r = q.top().se;
                    q.pop();
                    if(r - l + 1 >= size){//余る
                        q.push(make_pair(l + size, r));
                        m[num].push_back(make_pair(l, l + size - 1));
                        size = 0;
                    }else{//足りない
                        m[num].push_back(make_pair(l, r));
                        size -= (r - l + 1);
                    }
                }
            }else if(c == 'D'){
                int num; cin >> num;
                for(auto u : m[num]){
                    q.push(make_pair(u.fi, u.se));
                }
                m[num].erase(all(m[num]));
            }else{
                int idx; cin >> idx;
                bool flag = false;
                each(it, m){
                    auto key = it->fi;
                    auto v = it->se;
                    for (int i = 0; i < v.size(); ++i){
                        if(v[i].fi <= idx && idx <= v[i].se){
                            printf("%d\n", key);
                            flag = true;
                            break;
                        }
                    }
                    if(flag) break;
                }
                if(!flag){
                    printf("-1\n");
                }
            }
        }
        printf("\n");
    }
    return 0;
}