QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#351994#5470. Hasty Santa Clauswarner1129#WA 1ms3840kbC++202.3kb2024-03-12 18:50:142024-03-12 18:50:14

Judging History

你现在查看的是最新测评结果

  • [2024-03-12 18:50:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2024-03-12 18:50:14]
  • 提交

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)