QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#295554 | #6337. Mizuyokan 2 | Max_s_xaM | 0 | 966ms | 297416kb | C++14 | 5.0kb | 2023-12-31 11:59:44 | 2023-12-31 11:59:44 |
Judging History
answer
#include <iostream>
#include <algorithm>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
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
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
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 <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 25e4 + 10, MAXM = 5e4 + 10;
const int MAXB = 70, B = 65, INF = 1e6;
int n, q, a[MAXN];
int nxt[MAXN];
struct Node
{
int l, r;
int d[MAXB], p[MAXB];
void Clear() {for (int i = 0; i <= B; i++) d[i] = 0, p[i] = INF;}
Node operator + (const Node a) const
{
// cout << l << " " << r << " " << a.l << " " << a.r << "\n";
Node b;
b.l = l, b.r = a.r;
for (int i = 0; i <= B; i++)
{
if (l + i <= r)
{
if (p[i] == INF) b.d[i] = 0, b.p[i] = INF;
else if (a.p[p[i] - r - 1] == INF) b.d[i] = d[i], b.p[i] = p[i];
else b.d[i] = d[i] + a.d[p[i] - r - 1], b.p[i] = a.p[p[i] - r - 1];
}
else b.d[i] = a.d[l + i - r - 1], b.p[i] = a.p[l + i - r - 1];
// cout << b.d[i] << " " << b.p[i] << "\n";
}
return b;
}
}tr[MAXN << 2];
void Update(int cur, int l, int r, int x, int y)
{
if (l == r) tr[cur].Clear(), tr[cur].l = tr[cur].r = l, tr[cur].d[0] = (nxt[l] != INF), tr[cur].p[0] = nxt[l];
else
{
int mid = l + r >> 1;
if (x <= mid) Update(cur << 1, l, mid, x, y);
if (y > mid) Update(cur << 1 | 1, mid + 1, r, x, y);
tr[cur] = tr[cur << 1] + tr[cur << 1 | 1];
}
}
Node Query(int cur, int l, int r, int x, int y)
{
if (x <= l && r <= y) return tr[cur];
int mid = l + r >> 1;
if (y <= mid) return Query(cur << 1, l, mid, x, y);
if (x > mid) return Query(cur << 1 | 1, mid + 1, r, x, y);
return Query(cur << 1, l, mid, x, y) + Query(cur << 1 | 1, mid + 1, r, x, y);
}
int main()
{
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n);
for (int i = 1; i <= n; i++) Read(a[i]);
nxt[n + 1] = 1e6;
for (int i = n; i >= 0; i--)
{
nxt[i] = nxt[i + 1];
int sum = 0;
for (int j = i + 1; j <= n && j <= i + B; j++)
{
sum += a[j];
if (sum > a[i] && sum > a[j + 1]) {nxt[i] = min(nxt[i], j + 1); break;}
}
}
Update(1, 0, n, 0, n);
Read(q);
int x, k, l, r;
while (q--)
{
Read(x), Read(k), Read(l), Read(r);
a[x] = k;
for (int i = x; i >= x - B && i >= 0; i--)
{
nxt[i] = nxt[i + 1];
int sum = 0;
for (int j = i + 1; j <= n && j <= i + B; j++)
{
sum += a[j];
if (sum > a[i] && sum > a[j + 1]) {nxt[i] = min(nxt[i], j + 1); break;}
}
}
Update(1, 0, n, max(1, x - B), x);
int L = ++l, R = r, sum = 0;
while (L <= r && sum <= a[L]) sum += a[L++];
sum = 0;
while (R >= l && sum <= a[R]) sum += a[R--];
auto res = Query(1, 0, n, l, r);
int ans = max(1, res.d[0] * 2 - 1);
if (L <= r) res = Query(1, 0, n, L, r), ans = max(ans, res.d[0] * 2);
if (l <= R) res = Query(1, 0, n, l, R), ans = max(ans, res.d[0] * 2);
if (L <= R) res = Query(1, 0, n, L, R), ans = max(ans, res.d[0] * 2 + 1);
Write(ans, '\n');
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 1ms
memory: 3940kb
input:
170 581553716 290776853 145388421 581553716 168947671 936760822 849346471 126291564 133104657 125887494 136786623 123143788 137803872 129733949 849346471 880499329 202732710 611312524 152828126 305656257 611312524 121295297 6875889 74507235 419967909 333601507 281557968 740824934 370412466 185206229...
output:
59 56 61 61 56 37 42 46
result:
ok 8 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3948kb
input:
200 517847507 258923750 129461870 517847507 106915073 712580593 512811829 12657894 12715954 12534704 12759073 12554236 12685369 12563357 12817887 12534566 12752501 12518874 12746471 12524663 12730053 12586182 12803851 12628464 12778716 12645600 12701929 12550298 12754947 12548765 12765210 12592487 1...
output:
118 162 114 113 143 105 109 165 139 152
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
156 689580506 344790254 172395128 689580506 344790254 689580506 344790252 172395125 86197561 86197567 86197565 86197566 43098784 86197566 86197565 86197567 86197561 172395125 344790252 689580506 344790254 689580506 172395128 344790254 689580506 3985467 453082635 861305238 430652620 215326311 8613052...
output:
19 26 27 21 15 11
result:
ok 6 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
200 545371756 272685879 136342940 545371756 272685879 545371756 272685877 136342937 68171467 68171474 68171472 68171473 34085737 68171473 68171472 68171474 68171467 136342937 272685877 545371756 272685879 545371756 136342940 272685879 545371756 327464463 455363267 859187150 429593576 214796789 85918...
output:
27 36 25 26 16 11 15 21 19 22
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
200 433494437 165580141 63245986 24157817 9227465 3524578 1346269 514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2 1 1 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 102334155 267914296 701408733 863735928 433494437 165580141 632459...
output:
5 13 5 5 8 5 13 5 5 6
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
187 433494437 165580141 63245986 24157817 9227465 3524578 1346269 514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2 1 1 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 102334155 267914296 701408733 868260277 433494437 165580141 632459...
output:
4 36 18 10 19 11 3 29
result:
ok 8 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
200 942616273 418940008 209470430 104734784 104734784 104735481 523675545 247785 701408733 267914296 102334155 39088169 14930352 5702887 2178309 832040 317811 121393 46368 17711 6765 2584 987 377 144 55 21 8 3 1 1 1 2 5 13 34 89 233 610 1597 4181 10946 28657 75025 196418 514229 1346269 3524578 92274...
output:
5 21 8 5 9 8 20 17 5 5
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3948kb
input:
200 641304094 22086510 5470810 2634455 1317187 658631 329083 126285 49415 22321 11410 5273 359 133 50 20 9 3 3 3 9 30 79 220 585 1226 2467 4851 27355 76469 202803 2836339 8307675 16614893 38701275 77401954 154804637 309608784 619217509 353775485 433494437 165580141 63245986 24157817 9227465 3524578 ...
output:
5 13 9 9 9 4 12 12 11 5
result:
ok 10 numbers
Test #9:
score: -6
Wrong Answer
time: 1ms
memory: 3776kb
input:
200 433494437 165580141 63245986 24157817 9227465 3524578 1346269 514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2 1 1 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 102334155 267914296 701408733 693739790 701408733 267914296 102334...
output:
5 5 5 4 5 3 9 19 8 16
result:
wrong answer 9th numbers differ - expected: '9', found: '8'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #59:
score: 0
Wrong Answer
time: 953ms
memory: 296876kb
input:
185137 895278847 447639418 223819705 895278847 25847602 892542542 725274571 68345857 72124244 67050536 71135605 66549838 72378749 66083078 72261084 67667076 70423484 68942136 725274571 798132375 68764887 958288578 703862250 55104628 58120315 54690522 57110282 54279470 56516680 54581941 58474132 5445...
output:
59 26 80 55 43 41 79 37 57 79 69 29 31 25 26 76 32 25 27 36 34 39 67 40 67 71 45 40 49 52 64 61 29 40 39 34 41 19 28 51 31 43 62 23 31 26 73 39 63 36 53 27 46 56 30 67 60 37 71 22 42 59 67 87 16 27 20 38 14 64 20 19 41 34 55 53 15 51 43 29 71 60 49 9 76 18 86 29 73 61 38 46 21 62 20 20 67 71 83 82 5...
result:
wrong answer 17692nd numbers differ - expected: '53', found: '52'
Subtask #5:
score: 0
Wrong Answer
Test #76:
score: 29
Accepted
time: 862ms
memory: 297232kb
input:
235469 96936 48463 24226 96936 25951 73765 63933 7121 7884 7166 7731 7464 7559 7300 7767 7314 63933 88750 6093 115886 111307 16371 17529 15944 17376 16099 18186 15910 111307 116042 13997 111982 95565 10713 11748 10849 11375 11093 11406 10874 11810 11197 95565 98914 1302 65917 16473 32953 65917 15943...
output:
34 56 73 61 41 13 74 46 33 33 14 53 36 46 18 63 65 79 72 15 20 57 66 83 19 46 62 58 44 76 76 68 41 56 9 29 59 73 64 21 63 33 29 62 27 36 20 65 54 71 29 47 13 32 48 74 64 75 79 17 24 49 20 41 57 17 23 67 67 18 19 54 63 74 72 45 61 30 27 60 33 36 49 49 24 56 42 60 20 53 32 75 44 57 17 34 71 45 25 39 2...
result:
ok 44829 numbers
Test #77:
score: -29
Wrong Answer
time: 966ms
memory: 297416kb
input:
250000 88054 44025 22011 88054 6068 106051 104212 1356 1371 1362 1370 1361 1371 1358 1371 1357 1364 1354 1367 1362 1371 1361 1365 1359 1363 1357 1370 1361 1366 1360 1363 1357 1369 1358 1367 1358 1371 1355 1371 1359 1371 1360 1370 1359 1371 1357 1363 1357 1370 1355 1371 1360 1366 1355 1368 1358 1364 ...
output:
146 118 301 455 177 65 187 177 317 351 366 219 382 117 178 136 157 405 245 166 285 271 202 376 120 97 326 95 369 194 221 167 206 73 197 372 117 237 176 128 69 101 449 215 261 410 85 169 257 312 285 297 227 181 423 298 205 371 416 343 301 406 122 335 296 222 190 365 429 433 205 389 223 227 281 357 16...
result:
wrong answer 5863rd numbers differ - expected: '121', found: '120'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%