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; }