QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#295550#6337. Mizuyokan 2Max_s_xaM0 379ms198264kbC++145.0kb2023-12-31 11:39:532023-12-31 11:39:53

Judging History

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

  • [2023-12-31 11:39:53]
  • 评测
  • 测评结果:0
  • 用时:379ms
  • 内存:198264kb
  • [2023-12-31 11:39: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 = 45, B = 40, 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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7840kb

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: 379ms
memory: 197000kb

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: 331ms
memory: 198264kb

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%