読者です 読者をやめる 読者になる 読者になる

AtCoderBegginnerContest #005 C: おいしいたこ焼きの売り方

問題
Aの発生と消失の中でBが可能か判定するタイプのシミュレート問題(参考: AOJ0231 Dangerous Bridge)

解法
pair(時間, 種類) で入力を vector > につめる。シミュレートに queue を使う。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;

int main() {
  vector<Pii> timeline;
  int T; cin >> T;
  int N; cin >> N;
  for(int i=0; i<N; i++) {
    int a; cin >> a;
    timeline.push_back(Pii(a, 1));
    timeline.push_back(Pii(a+T, 3));
  }
  
  int M; cin >> M;
  for(int j=0; j<M; j++) {
    int b; cin >> b;
    timeline.push_back(Pii(b, 2));
  }
  
  sort(timeline.begin(), timeline.end());
  
  queue<int> Q;
  for(int i=0; i<timeline.size(); i++) {
    if(timeline[i].second == 1) {
      Q.push(timeline[i].first);
    }
    if(timeline[i].second == 2) {
      if(Q.empty()) {
	cout << "no" << endl;
	return 0;
      }
      Q.pop();
    }
    if(timeline[i].second == 3) {
      if(!Q.empty() && Q.front() + T == timeline[i].first) {
	Q.pop();
      }
    }
  }
  
  cout << "yes" << endl;
  
  return 0;
}