ferinの競プロ帳

競プロについてのメモ

Codeforces Round #594 (Div. 1) C. Queue in the Train

問題ページ
基本的にやるべきことは問題文に書いてあるのでそのシミュレーションを行う.ただし,0 \leq t \leq 10^9 の範囲で t を1ずつ増やしてシミュレーションをすると当然TLEなので,シミュレーションに関わってくる重要な時刻のみ取り扱う.人が席を立つ時刻 t_i と水を汲み終わる時刻において状況が変化する.この時刻は O(n) 個しか存在しないため,高速にシミュレーションができる.

席を立てる人の集合 \text{can},席を離れている人の集合 \text{leave},tankの前に並んでいる列 \text{que} を持ちながら時刻を進めていく.priority_queueに状況が変わる時刻を追加し,最も早い時刻を取り出すとすれば,時刻を進める処理を実装できる.時刻 t が席を立つ時刻なのか水を汲み終わる時刻なのかで処理が変わる.

  • 席を立つ時刻
    集合 \text{can} に席を立つ人を追加する.
  • 水を汲み終わる時刻
    今水を汲んでいる人が汲み終わる時刻として記録し,\text{leave}, \text{que} からその人を取り除く.\text{que} にまだ人が並んでいるのであれば,その人が水を汲み始めるとする.

この処理のあと,\text{can} の中で最も左にいる人が列に並ぶ条件を満たしているか?を判定する.列に並ぶならば,\text{can} から削除,\text{leave} に追加,\text{que} の最後尾に追加の処理を行うといった処理を行えばよい.

シミュレーションを行い時刻を進めるのに必要になる集合や列が何か?をしっかり整理して各時刻で行うべき処理をちゃんと詰める

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, p;  
    cin >> n >> p;  
    vector<ll> t(n);  
    REP(i, n) cin >> t[i];  
  
    using V = vector<ll>;  
    priority_queue<V, vector<V>, greater<V>> event;  
    REP(i, n) event.push({t[i], 0, i});  
  
    queue<ll> que;      // tankの前の列  
    set<ll> can, leave; // 席を離れられる人, 席を離れてる人  
    vector<ll> ans(n);  
  
    while(event.size()) {  
        V v = event.top(); event.pop();  
        ll time = v[0], type = v[1], index = v[2];  
  
        if(type == 1) {  
            ans[index] = time;  
            leave.erase(index);  
            que.pop();  
            if(que.size()) event.push({time+p, 1, que.front()});  
        } else {  
            can.insert(index);  
        }  
  
        if(can.size()) {  
            ll first = *can.begin();  
            if(leave.size() == 0 || *leave.begin() > first) {  
                can.erase(first);  
                leave.insert(first);  
                que.push(first);  
                if(que.size() == 1) event.push({time+p, 1, que.front()});  
            }  
        }  
    }  
  
    REP(i, n) cout << ans[i] << (i==n-1?'\n':' ');  
    cout << flush;  
  
    return 0;  
}  
``