Skip to content

Gym102452I - Incoming Asteroids

题解约 1.4 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

The International Coalition to Prevent Catastrophes (ICPC) recently discovered several small asteroids in a nearby galaxy. If these asteroids hit the Earth, it will lead to a terrible disaster. So it is important for the ICPC to fully study the orbit trajectories of these asteroids. The ICPC consists of many member states, and due to the difference in development, they may have different goals in the study.

Orbits of Comet Kohoutek and the Earth. Public domain.

The ICPC has marked nn astronomy observatories around the world, labelled by 1,2, ,n1,2,\cdots,n. According to the ICPC’s prediction, there will be mm events of two types, detailed below:

  • 「1 y k q[1…k]」 (1y1061\leq y\leq 10^6, 1k31\leq k\leq 3, 1qin for 1ik1\leq q_i\leq n\text{ for } 1 \le i \le k): A new member of the ICPC joins the study, whose goal is to gather at least yy minutes of video of the asteroids in total. The new member has kk cameras and is going to install exactly one camera in each astronomy observatory labelled by q1,q2,,qkq_1,q_2,\dots,q_k. It is guaranteed that these kk integers q1,q2,,qkq_1,q_2,\dots,q_k are pairwise distinct. Let pp be the number of events of type 1 before this event, then this member is assigned the ID of p+1p+1.
  • 「2 x y」 (1xn1\leq x\leq n, 1y1061\leq y\leq 10^6): Each the camera installed at the xx-th astronomy observatory successfully gathers yy minutes of asteroid video. You need to report the number of ICPC members whose goals are just reached after this event, and the IDs of these members. Note that you shouldn’t count the members whose goals have already been reached before this event.

You are an employee at the ICPC and your leader asks you to write a program to simulate these events, so that the ICPC may make appropriate preparations for the study.

#输入格式

The input contains only a single case.

The first line of the input contains two integers nn and mm (1n,m21051 \leq n,m \leq 2\cdot 10^5), denoting the number of astronomy observatories and the number of events. Each of the next mm lines describes an event in formats described in the statement above, except that some parameters are encrypted in order to enforce online processing.

Let lastlast be the number of members you report in the last event of the second type. Note that last=0last=0 before the first event of the second type is processed. For events of the first type, yy and qi (1ik)q_i \ (1\le i \le k) are encrypted. The actual values of yy and qiq_i are ylasty\oplus last and qilastq_i\oplus last. For events of the second type, x,yx,y are encrypted. The actual values of x,yx,y are xlastx\oplus last, ylasty \oplus last. In the expressions above, the symbol 「\oplus」 denotes the bitwise exclusive-or operation. Also note that the constraints described in the statement above apply to the corresponding parameters only after decryption, the encrypted values are not subject to those constraints.

#输出格式

For each event of the second type, print a single line. In this line, print an integer cntcnt first, denoting the number of ICPC members whose goals are just reached after this event. Then print cntcnt ascending integers, denoting the IDs of these ICPC members.

#输入输出样例

样例输入 #1

3 5
1 5 3 1 2 3
2 2 1
1 2 2 1 2
2 3 1
2 1 3

样例输出 #1

0
0
2 1 2

#思路

对于每一个观测者可以设置提醒闹钟,在 yk\lceil \frac{y}{k} \rceil 后检查是否满足结束条件。然后对于每一个观测站使用 std::set 或者 std::priority_queue 维护其闹钟序列即可。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cmath>
#include <functional>
#include <queue>
#include <set>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e5 + 5;

int n, m, lst, cnt;
long long a[N], b[N];
std::priority_queue<
std::pair<long long, int>,
std::vector<std::pair<long long, int>>,
std::greater<std::pair<long long, int>>>
q[N];
std::vector<int> ids[N];

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> m;

while (m--) {
int op;

cin >> op;

if (op == 1) {
int y, k;

cin >> y >> k;

a[++cnt] = y ^= lst;
int v = std::ceil(static_cast<double>(y) / k);

for (int i = 1, x; i <= k; i++) {
cin >> x;

ids[cnt].emplace_back(x ^= lst);
a[cnt] += b[x];
q[x].emplace(b[x] + v, cnt);
}
} else { // op == 2
int x, y;
std::set<int> ans;

cin >> x >> y;

b[x ^= lst] += y ^= lst;

while (!q[x].empty() && q[x].top().first <= b[x]) {
int id = q[x].top().second;
q[x].pop();

if (!a[id]) continue;

long long rest = a[id];
for (int p : ids[id]) {
rest -= b[p];
}

if (rest <= 0) {
ans.emplace(id);
a[id] = 0;
} else {
int v = std::ceil(static_cast<double>(rest) / ids[id].size());

for (int p : ids[id]) {
q[p].emplace(b[p] + v, id);
}
}
}

cout << (lst = ans.size());
for (int x : ans) cout << ' ' << x;
cout << endl;
}
}

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cmath>
#include <functional>
#include <set>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e5 + 5;

int n, m, lst, cnt;
long long a[N], b[N];
std::set<std::pair<long long, int>> q[N];
std::vector<std::pair<int, std::set<std::pair<long long, int>>::iterator>> ids[N];

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> m;

while (m--) {
int op;

cin >> op;

if (op == 1) {
int y, k;

cin >> y >> k;

a[++cnt] = y ^= lst;
int v = std::ceil(static_cast<double>(y) / k);

for (int i = 1, x; i <= k; i++) {
cin >> x;

x ^= lst;
ids[cnt].emplace_back(x, q[x].emplace(b[x] + v, cnt).first);
a[cnt] += b[x];
}
} else { // op == 2
int x, y;
std::set<int> ans;

cin >> x >> y;

b[x ^= lst] += y ^= lst;

while (!q[x].empty() && q[x].begin()->first <= b[x]) {
int id = q[x].begin()->second;

long long rest = a[id];
for (auto o : ids[id]) {
rest -= b[o.first];
q[o.first].erase(o.second);
}

if (rest <= 0) {
ans.emplace(id);
ids[id].clear();
} else {
int v = std::ceil(static_cast<double>(rest) / ids[id].size());

for (auto &o : ids[id]) {
o.second = q[o.first].emplace(b[o.first] + v, id).first;
}
}
}

cout << (lst = ans.size());
for (int x : ans) cout << ' ' << x;
cout << endl;
}
}

return 0;
}