QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #455720 | #7626. Quake and Rebuild | Rong7 | WA | 69ms | 8276kb | C++14 | 7.2kb | 2024-06-26 18:55:19 | 2024-06-26 18:55:19 |
Judging History
answer
// Not afraid to dark.
#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;
clock_t start_time, end_time;
#define GET_START start_time = clock ();
#define GET_END end_time = clock (); fprintf (stderr, "TIME COSSEMED : %0.3lf\n", 1.0 * (end_time - start_time) / CLOCKS_PER_SEC);
#define inline __inline__ __attribute__ ((always_inline))
static char buf[1000000], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1 ++)
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
inline char gc() {
#if DEBUG // 调试，可显示字符
return getchar();
#endif
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
return p1 == p2 ? ' ' : *p1++;
}
inline bool blank(char ch) {
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
template <class T>
inline void read(T &x) {
double tmp = 1;
bool sign = 0;
x = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
if (ch == '.')
for (ch = gc(); isdigit(ch); ch = gc())
tmp /= 10.0, x += tmp * (ch - '0');
if (sign) x = -x;
}
inline void read(char *s) {
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
}
inline void read(char &c) { for (c = gc(); blank(c); c = gc()); }
inline void push(const char &c) {
#if DEBUG // 调试，可显示字符
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <class T>
inline void write(T x) {
if (x < 0) x = -x, push('-'); // 负数输出
static T sta[35];
T top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}
template <class T>
inline void write(T x, char lastChar) {
write(x), push(lastChar);
}
} io;
const int N = 2.5e5, T = 600;
int n, m;
namespace BLOCK {
int sq, len, block[N + 5], delta[T + 5], bl[T + 5], br[T + 5];
bool tag[N + 5];
int f[N + 5], nx[N + 5], cs[N + 5];
bool ton[N + 5];
inline void rebuild (int x){
for (int i = bl[x];i <= br[x];++ i){
if (f[i] - delta[x] < bl[x])
nx[i] = max (0, f[i] - delta[x]), cs[i] = 1;
else
nx[i] = nx[f[i] - delta[x]], cs[i] = cs[f[i] - delta[x]] + 1;
}
tag[x] = false;
}
inline void build (){
sq = (int) sqrt (n);
len = n / sq;
if (sq * len < n)
++ len;
for (int i = 1;i <= sq;++ i){
bl[i] = br[i - 1] + 1;
br[i] = min (n, bl[i] + len - 1);
for (int j = bl[i];j <= br[i];++ j)
block[j] = i;
delta[i] = 0;
rebuild (i);
}
}
inline int nex (int x){
if (delta[block[x]] < len)
return nx[x];
return max (0, f[x] - delta[block[x]]);
}
inline int F (int x){
return max (0, f[x] - delta[block[x]]);
}
inline int cos (int x){
if (delta[block[x]] < len)
return cs[x];
return 1;
}
vector < int > pt[T + 5];
} using namespace BLOCK;
signed main (){
// GET_START
io.read (n), io.read (m), -- n;
for (int i = 1;i <= n;++ i)
io.read (f[i]), -- f[i];
build ();
while (m --){
int op;
io.read (op);
if (op == 1){
int l, r, d;
io.read (l), io.read (r), io.read (d);
-- l, -- r;
if (! d)
continue;
for (int i = l;i <= min (r, br[block[l]]);++ i)
f[i] = max (0, f[i] - d);
tag[block[l]] = true;
for (int i = block[l] + 1;i < block[r];++ i){
delta[i] = min (delta[i] + d, n);
if (delta[i] < len)
tag[i] = true;
}
if (block[l] ^ block[r]){
for (int i = bl[block[r]];i <= r;++ i)
f[i] = max (0, f[i] - d);
tag[block[r]] = true;
}
} else {
int N, tx, ans = 0, cnt = N;
io.read (N);
while (N --){
io.read (tx);
-- tx;
pt[block[tx]].push_back (tx);
}
for (int i = sq;i >= 1;-- i)
if (! pt[i].empty ()){
if (tag[i] && delta[block[i]] < len)
rebuild (i);
for (int x : pt[i])
ton[x] = true;
vector < int > lins;
for (int x : pt[i])
if (ton[x]){
ton[x] = false;
lins.push_back (x);
} else
-- cnt;
pt[i] = lins, lins.clear ();
if (cnt == 1){
pt[i].clear ();
++ ans;
break;
}
bool tag = false;
for (int x : pt[i]){
if (! ton[nex (x)])
ton[nex (x)] = true;
else
tag = true;
}
for (int x : pt[i])
ton[nex (x)] = false;
if (! tag){
for (int x : pt[i]){
pt[block[nex (x)]].push_back (nex (x));
ans += cos (x);
}
pt[i].clear ();
} else {
int minx = br[i];
for (int x : pt[i])
ton[x] = true, minx = min (minx, x);
cnt -= (int) pt[i].size ();
pt[i].clear ();
for (int j = br[i];j >= bl[i];-- j)
if (ton[j]){
++ ans;
if (j > minx || cnt > 0){
if (F (j) >= bl[i])
ton[F (j)] = true;
else {
pt[block[F (j)]].push_back (F (j));
++ cnt;
}
minx = min (minx, F (j));
}
}
for (int j = bl[i];j <= br[i];++ j)
ton[j] = false;
}
}
if (! pt[0].empty ())
++ ans, pt[0].clear ();
io.write (ans, '\n');
}
}
// GET_END
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7696kb
input:
4 5 1 2 2 2 2 1 4 1 2 3 1 2 3 2 3 4 1 4 4 1 2 2 3 4
output:
3 4 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 7664kb
input:
10 10 1 2 3 3 4 5 7 7 9 1 2 10 3 2 9 9 5 3 10 7 2 4 6 8 1 6 10 3 1 2 7 3 1 7 10 3 2 2 4 3 2 3 7 4 4 1 3 9 3 1 3 9 3 1 10 10 3
output:
10 3 3
result:
ok 3 lines
Test #3:
score: -100
Wrong Answer
time: 69ms
memory: 8276kb
input:
3051 198219 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...
output:
78 78 70 64 60 55 60 58 52 54 51 53 56 51 51 57 55 52 49 55 49 50 53 49 49 48 49 48 53 50 50 54 47 52 45 49 49 46 47 48 49 50 48 49 47 48 47 49 48 50 48 49 48 47 49 48 51 48 48 45 45 46 50 50 50 48 49 46 47 47 46 48 48 47 49 47 46 47 46 47 46 45 47 49 49 50 51 48 48 49 47 47 48 50 46 47 48 50 46 47 ...
result:
wrong answer 3547th lines differ - expected: '45', found: '43'