QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#295557#6337. Mizuyokan 2Max_s_xaM0 978ms297640kbC++145.0kb2023-12-31 12:29:532023-12-31 12:29:54

Judging History

你现在查看的是最新测评结果

  • [2023-12-31 12:29:54]
  • 评测
  • 测评结果:0
  • 用时:978ms
  • 内存:297640kb
  • [2023-12-31 12:29:53]
  • 提交

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(0, 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: 3768kb

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: 3768kb

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: 3704kb

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: 3900kb

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: 1ms
memory: 3712kb

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: 3712kb

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: 3944kb

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: 3944kb

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: 0ms
memory: 3944kb

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: 918ms
memory: 296864kb

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: 863ms
memory: 297256kb

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: 978ms
memory: 297640kb

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%