QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#877012#8302. Incoming AsteroidsNianFengRE 2ms28484kbC++144.3kb2025-01-31 17:28:142025-01-31 17:28:15

Judging History

This is the latest submission verdict.

  • [2025-01-31 17:28:15]
  • Judged
  • Verdict: RE
  • Time: 2ms
  • Memory: 28484kb
  • [2025-01-31 17:28:14]
  • Submitted

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...

output:


result: