QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#351994 | #5470. Hasty Santa Claus | warner1129# | WA | 1ms | 3840kb | C++20 | 2.3kb | 2024-03-12 18:50:14 | 2024-03-12 18:50:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <ranges::range T,
class = enable_if_t<!is_convertible_v<T, string_view>>>
istream &operator>>(istream &s, T &&v) {
for (auto &&x : v)
s >> x;
return s;
}
template <ranges::range T,
class = enable_if_t<!is_convertible_v<T, string_view>>>
ostream &operator<<(ostream &s, T &&v) {
for (auto &&x : v)
s << x << ' ';
return s;
}
#ifdef LOCAL
template <class... T> void dbg(T... x) {
char e{};
((cerr << e << x, e = ' '), ...);
}
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
template <class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
template <class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template <class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 mod = 1e9 + 7;
void solve() {
int n, k;
cin >> n >> k;
vector<pair<int, int>> seg(n);
for (auto &[l, r] : seg) {
cin >> l >> r;
}
vector<int> ans(n);
vector<int> ord(n);
iota(all(ord), 0);
sort(all(ord), [&](int a, int b) {
return seg[a] < seg[b];
});
int cur = -1;
int cnt = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int ti = 0;
for (int r = 0; r < n;) {
while(pq.empty() && seg[r].ff > ti) ++ti;
while(r < n && seg[ord[r]].ff <= ti){
pq.push(make_pair(seg[ord[r]].ss, ord[r]));
++r;
}
for(int j = 0; j < k && !pq.empty(); j++){
ans[pq.top().second] = ti;
pq.pop();
}
++ti;
}
while(!pq.empty()){
for(int i = 0; i < k && !pq.empty(); i++){
ans[pq.top().second] = ti;
pq.pop();
}
++ti;
}
for (int x : ans) {
cout << x << '\n';
}
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin.exceptions(cin.failbit);
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3828kb
input:
5 1 23 25 23 27 24 25 25 25 25 26
output:
23 27 24 25 26
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
7 2 1 31 1 31 1 31 1 31 1 31 1 31 1 31
output:
1 1 2 2 3 3 4
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
6 2 24 25 24 25 24 25 25 26 25 26 25 26
output:
24 24 25 25 26 26
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
20 5 9 26 7 29 7 30 4 30 4 27 19 30 8 27 13 25 6 29 1 25 8 31 2 29 13 25 9 26 8 31 1 28 8 26 3 26 5 25 1 28
output:
9 11 11 11 10 19 10 13 11 9 12 11 13 9 12 10 9 10 9 10
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
100 5 9 25 2 30 2 31 4 29 2 25 1 27 7 26 3 25 15 30 2 26 9 26 2 30 6 30 24 31 7 28 15 27 2 29 23 31 18 29 23 31 1 31 2 27 7 29 2 27 23 31 16 31 17 31 10 29 4 30 3 26 2 26 19 28 1 30 8 30 4 31 10 29 1 31 22 30 6 29 3 26 3 30 5 28 1 31 9 28 2 30 2 26 13 30 4 25 2 27 1 25 5 27 5 26 9 27 1 28 19 31 5 31...
output:
9 19 23 16 9 12 10 9 20 10 10 20 20 24 14 15 16 24 18 24 24 13 16 13 24 25 25 17 20 10 11 19 20 21 25 17 25 22 17 11 21 14 26 14 21 11 21 9 13 9 13 11 13 14 26 26 26 26 23 15 15 21 17 11 27 22 22 27 12 15 22 17 15 27 22 12 18 12 27 27 28 18 16 18 28 14 16 12 25 18 23 23 28 28 19 19 10 19 23 28
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
100 50 3 27 6 25 1 31 2 29 24 31 5 31 14 31 9 25 11 26 25 30 7 30 24 28 10 30 2 26 1 26 1 25 6 31 23 31 5 28 4 28 2 25 1 26 4 30 6 27 7 29 11 31 3 29 23 28 3 26 4 31 10 29 1 30 8 25 17 25 7 25 8 28 23 29 1 27 1 25 6 30 1 29 13 25 5 30 1 30 1 29 2 31 9 27 4 25 1 31 1 25 18 31 3 27 12 31 7 29 13 30 1 ...
output:
3 6 3 3 24 5 14 9 11 25 7 24 10 3 3 3 6 23 5 4 3 3 4 6 7 11 3 23 3 4 10 3 8 17 7 8 23 3 3 6 3 14 5 3 3 3 9 4 3 3 20 3 14 7 14 3 3 9 6 14 3 8 3 3 3 16 3 3 10 21 3 4 9 20 3 11 7 9 14 3 6 5 7 3 4 3 20 7 20 5 3 3 9 8 20 3 3 22 3 20
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
100 100 9 25 3 25 24 31 4 31 2 29 2 31 22 30 18 30 3 25 6 29 19 31 3 30 15 31 1 27 20 30 4 26 5 25 23 30 11 31 20 26 13 25 3 27 8 25 1 25 15 31 13 30 24 29 3 27 22 27 14 29 4 30 11 31 21 30 2 29 12 27 25 28 20 28 5 30 1 30 6 30 2 27 11 28 18 29 4 26 1 26 7 29 18 30 1 26 18 29 2 28 1 25 1 26 9 31 4 2...
output:
9 9 24 9 9 9 22 18 9 9 19 9 15 9 20 9 9 23 11 20 13 9 9 9 15 13 24 9 22 14 9 11 21 9 12 25 20 9 9 9 9 11 18 9 9 9 18 9 18 9 9 9 9 9 25 14 13 9 9 18 9 9 14 9 9 9 9 9 9 9 24 19 9 22 9 9 9 9 9 9 19 11 9 9 9 9 9 13 16 13 9 9 9 9 9 9 9 18 10 13
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1000 50 11 30 4 29 2 26 1 31 3 27 23 29 5 26 4 27 5 28 11 26 2 28 18 27 1 31 8 28 6 25 5 25 14 31 3 27 4 26 16 27 4 31 9 31 6 29 8 27 8 25 3 29 17 27 2 28 9 29 2 31 11 31 12 30 2 30 2 31 19 31 7 26 18 27 9 31 1 27 8 25 8 28 2 27 10 28 7 26 5 31 8 26 12 30 19 31 25 29 2 31 1 31 6 29 4 29 11 27 21 30 ...
output:
23 20 12 26 15 23 13 15 18 13 18 18 26 18 11 11 26 15 13 16 26 26 20 15 11 20 17 18 20 27 27 23 23 27 27 13 18 27 15 11 18 15 18 13 27 13 23 27 25 27 27 20 20 15 23 23 13 17 15 15 27 13 13 27 27 15 23 21 23 11 13 13 12 27 24 23 21 27 13 13 24 21 20 21 13 24 27 14 24 21 13 18 13 27 18 15 15 27 13 11 ...
result:
ok ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
1000 100 8 28 11 29 9 30 1 28 17 25 20 29 6 26 15 25 1 28 12 30 6 31 10 31 4 27 15 28 4 31 10 25 5 30 4 25 19 31 17 27 5 28 6 31 6 31 3 29 1 29 10 31 9 30 9 31 1 31 10 31 5 28 25 29 15 27 4 31 3 31 18 27 1 31 11 26 4 30 24 29 4 31 1 27 4 25 7 31 2 26 3 31 19 31 1 28 7 25 4 27 9 27 13 26 5 26 12 30 6...
output:
10 11 12 10 17 20 8 15 10 12 14 14 9 15 14 10 12 8 19 17 10 14 14 11 11 14 12 14 14 14 10 25 15 14 14 18 14 11 13 24 14 9 8 14 8 14 19 10 8 9 9 13 8 13 11 14 14 11 14 8 9 14 14 10 14 20 21 8 17 13 21 20 13 11 11 9 13 19 22 13 8 8 10 9 11 13 8 10 8 19 8 14 14 15 9 14 22 8 8 14 18 9 8 13 17 13 8 10 13...
result:
ok ok
Test #10:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
1000 1000 14 31 5 29 7 27 4 26 1 27 10 30 17 31 5 31 8 30 10 28 3 29 18 31 7 31 4 30 7 29 5 28 4 31 19 27 5 27 20 29 15 27 10 29 2 27 4 27 4 25 5 29 4 27 13 27 3 31 9 30 11 30 3 31 10 26 2 30 24 31 19 31 13 27 1 31 6 26 17 26 1 31 13 31 10 30 1 30 16 26 3 25 15 27 2 31 6 28 4 26 7 26 1 31 12 25 19 2...
output:
14 14 14 14 14 14 23 14 14 14 14 23 14 14 14 14 14 23 14 23 23 14 14 14 14 14 14 14 14 14 14 14 14 14 24 23 14 14 14 23 14 14 14 14 23 14 23 14 14 14 14 14 14 23 14 23 14 23 14 14 14 23 14 14 23 14 14 14 14 14 14 14 14 14 23 14 23 23 14 14 14 14 14 14 14 23 14 23 14 14 14 14 14 14 14 14 23 14 14 14 ...
result:
ok ok
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3840kb
input:
31 1 21 25 25 26 18 25 11 25 25 27 20 25 23 25 19 25 25 31 10 25 1 25 25 25 8 25 16 25 17 25 14 25 4 25 22 25 12 25 5 25 15 25 7 25 2 25 25 30 25 28 6 25 24 25 9 25 13 25 25 29 3 25
output:
21 46 22 23 47 24 25 26 51 27 28 29 30 31 32 33 34 35 36 37 38 39 40 50 48 41 42 43 44 49 45
result:
wrong answer output line is not a valid date.(line = 46)