QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#877012 | #8302. Incoming Asteroids | NianFeng | RE | 2ms | 28484kb | C++14 | 4.3kb | 2025-01-31 17:28:14 | 2025-01-31 17:28:15 |
Judging History
answer
/* 年挽红枫,溪傍芦荻。*/
#ifdef DEBUG
#include <iostream>
#include <cmath>
#include <ctime>
bool Mbe;
void _Dihan();
#endif
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <queue>
#include <vector>
typedef long long i64;
typedef unsigned long long ull;
typedef double f32;
typedef long double ldb;
typedef __int128 i28;
typedef unsigned __int128 u28;
template <typename T> bool chkMx(T &x, T y) { return x < y ? x = y, true : false; }
template <typename T> bool chkMn(T &x, T y) { return x > y ? x = y, true : false; }
namespace IO {
#define file(s) freopen(#s".in", "r", stdin), freopen(#s".out", "w", stdout)
constexpr int SIZE = 1 << 21;
char ibuf[SIZE], *p1 = ibuf, *p2 = ibuf, obuf[SIZE], *p3 = obuf;
#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
#define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZE, stdin), p1 == p2) ? EOF : *p1++)
#define pc(ch) (p3 == obuf + SIZE && flush(), *p3++ = ch)
class Flush { public: ~Flush() { flush(); } } _;
auto chkChar = [](const char &c) -> bool { return c >= 'a' && c <= 'z'; };
template <typename T> inline void read(T &x) {
static char c;
static bool f;
x = 0, f = true;
while (!isdigit(c = gc())) if (c == '-') f = false;
while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
f || (x = ~(x - 1), 0);
}
inline void read(char &c) {
while (!chkChar(c = gc())) ;
}
inline void read(char *s) {
static char c;
while (!chkChar(c = gc())) ;
while (chkChar(c)) *s++ = c, c = gc();
*s = '\0';
}
template <typename T> inline void write(T x) {
static char stk[50];
static unsigned top;
x < 0 && (pc('-'), x = ~(x - 1), 1), top = 0;
do stk[++top] = x % 10 ^ 48; while (x /= 10);
while (top) pc(stk[top--]);
}
inline void write(char c) { pc(c); }
inline void write(char *s) { while (*s) pc(*s++); }
inline void write(const char *s) {
for (int i = 0; *(s + i); ++i) pc(*(s + i));
}
template <typename T, typename ...Args>
inline void read(T &first, Args &...args) { read(first), read(args...); }
template <typename T, typename ...Args>
inline void write(T first, Args ...args) { write(first), write(args...); }
}
using namespace IO;
constexpr int N = 2e5 + 5;
int n, m, cnt;
std::pair<int, std::vector<std::pair<int, i64> > > a[N];
i64 tag[N];
template <typename T> class MultiSet {
private:
std::priority_queue<T> num, del;
int sz;
public:
void insert(T x) { num.emplace(x), ++sz; }
void remove(T x) { del.emplace(x), --sz; }
T query() {
while (!del.empty() && num.top() == del.top())
num.pop(), del.pop();
return num.top();
}
bool check() { return sz; }
};
MultiSet<std::pair<i64, int> > s[N];
std::vector<int> res;
void update(int id) {
int cur = (a[id].first - 1) / a[id].second.size() + 1;
for (auto [p, k] : a[id].second) {
a[id].first -= tag[p] - k;
s[p].remove({k + cur, id});
}
if (a[id].first <= 0)
res.emplace_back(id);
else {
cur = (a[id].first - 1) / a[id].second.size() + 1;
for (auto &[p, k] : a[id].second) {
k = tag[p];
s[p].insert({k + cur, id});
}
}
}
int main() {
#ifdef DEBUG
file(cur);
#endif
read(n, m);
while (m--) {
static int opt, x, y, lst, cur;
read(opt, x, y), x ^= lst, y ^= lst;
switch (opt) {
case 1:
a[++cnt] = std::make_pair(
x, std::vector<std::pair<int, i64> >(y)
);
cur = (x - 1) / y + 1;
for (auto &[p, k] : a[cnt].second) {
read(p), k = tag[p];
s[p].insert({k + cur, cnt});
}
break;
case 2:
tag[x] += y;
while (s[x].check()) {
auto [k, id] = s[x].query();
if (k > tag[x]) break;
update(id);
}
std::sort(res.begin(), res.end());
write(lst = res.size());
for (int id : res)
write(' ', id);
write('\n');
break;
}
}
#ifdef DEBUG
_Dihan();
#endif
return 0;
}
#ifdef DEBUG
bool Med;
void _Dihan() {
std::cerr << "Memory: " << abs(&Med - &Mbe) / 1048576.0 << " MB\n";
std::cerr << "Time: " << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
}
#endif
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 28484kb
input:
3 5 1 5 3 1 2 3 2 2 1 1 2 2 1 2 2 3 1 2 1 3
output:
0 0 2 1 2
result:
ok 3 lines
Test #2:
score: -100
Runtime Error
input:
200000 200000 1 421386 1 122023 2 127573 97972 1 489180 1 197930 2 82505 59100 1 502097 3 91617 14193 139642 2 132931 74031 1 404862 1 36227 2 152826 8462 1 750072 2 51616 75416 2 1547 11479 1 255849 2 70036 41620 2 126414 17120 1 626334 3 97273 190595 174083 2 148803 132 1 407236 2 83898 5103 2 169...