mayoko’s diary

プロコンとかいろいろ。

CROC 2016 - Qualification B. Processing Queries

解法

しゃくとりっぽくやります。
区間 [lp, rp) の区間を見ている時, t[rp] より前の始まる仕事は全部片付けておきます。で, この時 queue に詰まれた仕事の数が b 未満なら, rp を仕事として追加します。一方, 仕事の数が b 以上なら, rp の仕事は無視して次に進みます。

const int MAXN = 200200;
const ll INF = 1ll<<60;
ll t[MAXN], d[MAXN], ans[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, b;
    cin >> n >> b;
    b++;
    for (int i = 0; i < n; i++) cin >> t[i] >> d[i];
    int lp = 0, rp = min(n, b), cnt = rp;
    ll time = 0;
    for (;;) {
        ll end = (rp < n ? t[rp] : INF);
        while (lp < rp) {
            if (ans[lp] == -1) {
                lp++;
                continue;
            }
            time = max<ll>(time, t[lp]);
            if (time+d[lp] > end) break;
            time += d[lp];
            ans[lp++] = time;
            cnt--;
        }
        if (rp == n) break;
        if (cnt >= b) {
            ans[rp++] = -1;
            continue;
        } else {
            rp++;
            cnt++;
        }
    }
    for (int i = 0; i < n; i++) cout << ans[i] << " ";
    cout << endl;
    return 0;
}