Restrictive Filesystem

問題

Restrictive Filesystem | Aizu Online Judge

考え

愚直に書くと、map<セクタ番号, 識別子>を作って，逐一更新して行くということになるでしょう。しかし、10⁹までのセクタにアクセスする可能性があるので、これではメモリ不足（MLE）と時間不足（TLE）になります。

MLE & TLE program

#include <iostream>
#include <map>
using namespace std;
#define ll long long

int main () {
  int n;
  while (cin >> n && n != 0) {
    string h;
    ll i, s;
    map<ll, ll> memory;
    for (int j = 0; j < n; j++) {
      cin >> h;
      
      // hについて場合分け
      if (h == "W") {
        cin >> i >> s;
        ll sub = 0;
        for (ll l = 0; l <= 1000000000; l++) {
          if (memory[l] == 0) {
            memory[l] = i + 1;
            sub++;
            if (sub == s) {
              break;  
            }    
          }
        }  
      }
      if (h == "D") {
        cin >> i;
        for (map<ll, ll>::iterator p = memory.begin(); p != memory.end(); ++p) {
          if (p->second == (i + 1)) {
            p->second = 0;  
          }  
        }  
      }
      if (h == "R") {
        cin >> s;
        cout << memory[s] - 1 << endl;  
      }
    }
    cout << endl;  
  }  
}

MLEとTLEは区間を指定することで解決することができます。つまり、map<識別子, vector<pairs<左側, 右側> > > >を作ることで解決します。とはいえ、実装が重いですね笑。結構時間がかかってしまいました。

Accepted program

#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long

int main () {
  int n;
  while (cin >> n && n != 0) {
    string h;
    ll i, s;
    map<ll, vector<pair<ll, ll> > > memory;
    for (int j = 0; j < n; j++) {
      cin >> h;
      if (h == "W") {
        cin >> i >> s;
        ll left, right;
        vector<pair<ll, ll> > sub;
        for (map<ll, vector<pair<ll, ll> > > ::iterator p = memory.begin(); p != memory.end(); ++p) {
          for (ll q = 0; q < p->second.size(); q++) {
            sub.push_back(p->second[q]);  
          }  
        }  
        sort(sub.begin(), sub.end());

        // itというのは、
        ll it = s;
        left = -1;
        right = -1;
        for (ll q = 0; q < sub.size(); q++) {
          left = sub[q].first;
          if (left == right + 1) {
            // right ~ leftまでで入る余地なし 
          }    
          else {

            // inputだけ挿入することが可能.
            ll input = left - right - 1;
            pair<ll, ll> subsub;
            if (it >= input) {

              // inputだけ挿入する
              subsub.first = right + 1;
              subsub.second = left - 1;
              it = it - input;
              memory[i].push_back(subsub);
            }
            else {
              subsub.first = right + 1;
              subsub.second = right + it; 
              it = 0;
              memory[i].push_back(subsub);
              break; 
            }
            if (it == 0) {
              break;
            }
          }
          right = sub[q].second;
        }
        if (it != 0) {
          pair<ll, ll> subsub;
          subsub.first = right + 1;
          subsub.second = right + it;
          memory[i].push_back(subsub);    
        }
      }
      if (h == "D") {
        cin >> i;
        memory[i].clear();  
      }
      if (h == "R") {
        cin >> s;
        bool ok = false;
        for (map<ll, vector<pair<ll, ll> > > ::iterator p = memory.begin(); p != memory.end(); ++p) {
          for (ll q = 0; q < p->second.size(); q++) {
            if (s >= p->second[q].first && s <= p->second[q].second) {
              ok = true;
              cout << p->first << endl;
              break;  
            }
          }  
          if (ok) {
            break;  
          }
        }  
        if (!ok) {
          cout << -1 << endl;  
        }
      }
    }  
    cout << endl;  
  }  
}