QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #455731 | #7626. Quake and Rebuild | Rong7 | WA | 62ms | 8980kb | C++14 | 6.3kb | 2024-06-26 19:02:52 | 2024-06-26 19:02:53 |
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 ++
namespace io {
int read_pos, read_dt; char read_char;
inline int read (int &p = read_pos){
p = 0, read_dt = 1; read_char = getchar ();
while (! isdigit (read_char)){
if (read_char == '-')
read_dt = - 1;
read_char = getchar ();
}
while (isdigit (read_char)){
p = (p << 1) + (p << 3) + read_char - 48;
read_char = getchar ();
}
return p = p * read_dt;
}
int write_sta[65], write_top;
inline void write (int x){
if (x < 0)
putchar ('-'), x = - x;
write_top = 0;
do
write_sta[write_top ++] = x % 10, x /= 10;
while (x);
while (write_top)
putchar (write_sta[-- write_top] + 48);
}
}
#define upp(x) ((x) < 0 ? 0 : (x))
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] = upp (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 (2.0 * 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 upp (f[x] - delta[block[x]]);
}
inline int F (int x){
return upp (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
n = io::read () - 1, io::read (m);
for (int i = 1;i <= n;++ i)
f[i] = io::read () - 1;
build ();
while (m --){
int op = io::read ();
if (op == 1){
int l = io::read () - 1, r = io::read () - 1, d = io::read ();
if (! d)
continue;
for (int i = l;i <= min (r, br[block[l]]);++ i)
f[i] = upp (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] = upp (f[i] - d);
tag[block[r]] = true;
}
} else {
int N = io::read (), tx, ans = 0, cnt = N;
while (N --){
tx = io::read () - 1;
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), puts ("");
}
}
GET_END
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7920kb
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: 8028kb
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: 62ms
memory: 8980kb
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 48 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 52nd lines differ - expected: '49', found: '48'