QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#295551 | #6337. Mizuyokan 2 | Max_s_xaM | 0 | 834ms | 297584kb | C++14 | 5.0kb | 2023-12-31 11:40:24 | 2023-12-31 11:40:25 |
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;}
}
}
// for (int i = 0; i <= n; i++) cout << nxt[i] << " "; cout << "\n";
Update(1, 0, n, max(1, x - B), x);
// cout << "Query\n";
auto res = Query(1, 0, n, l, r);
int ans = 1;
for (int i = 0; i <= B; i++)
{
if (res.p[i] == INF) continue;
// cout << res.d[i] << " " << res.p[i] << "\n";
if (res.p[i] == r + 1) ans = max(ans, res.d[i] * 2 - 1 + (i != 0));
else ans = max(ans, res.d[i] * 2 - 2 + (i != 0));
}
Write(ans, '\n');
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5812kb
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 55 60 60 56 37 42 46
result:
wrong answer 2nd numbers differ - expected: '56', found: '55'
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: 834ms
memory: 297584kb
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 78 37 57 79 69 29 31 24 26 76 32 25 27 36 34 39 66 40 67 71 44 40 48 52 64 61 28 40 39 34 39 18 28 51 31 43 62 23 31 26 72 39 62 36 53 27 46 56 30 67 60 37 71 22 41 58 66 86 16 27 19 37 14 64 20 19 41 33 55 53 15 51 43 29 71 59 49 9 76 18 86 29 73 61 38 46 21 61 20 20 67 71 82 82 5...
result:
wrong answer 7th numbers differ - expected: '79', found: '78'
Subtask #5:
score: 0
Wrong Answer
Test #76:
score: 0
Wrong Answer
time: 754ms
memory: 297576kb
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 55 73 61 41 13 74 46 33 33 14 53 36 46 18 63 65 78 72 14 20 55 66 82 19 46 62 58 44 76 75 68 41 56 9 29 57 73 64 21 63 33 29 62 27 36 20 65 54 71 29 47 13 32 48 74 64 75 79 17 23 49 20 41 57 16 23 67 66 18 19 54 63 74 71 45 61 30 26 60 33 36 49 49 24 56 42 59 20 53 32 75 44 57 17 34 70 45 25 39 2...
result:
wrong answer 2nd numbers differ - expected: '56', found: '55'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%