QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#788216	#9791. Intrusive Donkey	ucup-team3519^#	WA	0ms	3816kb	C++17	3.6kb	2024-11-27 16:14:45	2024-11-27 16:14:46

Judging History

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

[2024-11-27 16:14:46]
评测

测评结果：WA
用时：0ms
内存：3816kb

查看

[2024-11-27 16:14:45]
提交

answer

#include <bits/stdc++.h>

using i64 = int64_t;
using i128 = __int128_t;
constexpr i64 INF = 1.5e18;

constexpr int MAXN = 2e5 + 19;

i64 add(i64 a, i64 b) {
    return std::min(a + b, INF);
}
i64 mul(i64 a, i64 b) {
    return std::min<i128>((i128)a * b, INF);
}

struct Node {
    i64 sum, tag;
} tr[MAXN << 2];
void push_up(int node) {
    tr[node].sum = add(tr[node << 1].sum, tr[node << 1 | 1].sum);
}
void push_down(int node) {
    if (tr[node].tag != 1) {
        i64 &tag = tr[node].tag;
        
        tr[node << 1].sum = mul(tr[node << 1].sum, tag);
        tr[node << 1].tag = mul(tr[node << 1].tag, tag);
        tr[node << 1 | 1].sum = mul(tr[node << 1 | 1].sum, tag);
        tr[node << 1 | 1].tag = mul(tr[node << 1 | 1].tag, tag);
        
        tag = 1;
    }
}
void build(int node, int L, int R) {
    tr[node].tag = 1;
    if (L == R) {
        tr[node].sum = 1;
        return;
    }
    int mid = (L + R) / 2;
    build(node << 1, L, mid);
    build(node << 1 | 1, mid + 1, R);
    push_up(node);
}
int find(int node, int L, int R, i64 k) {
    if (L == R) return L;
    int mid = (L + R) / 2;
    push_down(node);
    if (tr[node << 1].sum >= k) return find(node << 1, L, mid, k);
    else return find(node << 1 | 1, mid + 1, R, k - tr[node << 1].sum);
}
i64 query(int node, int L, int R, int l, int r) {
    if (l <= L && R <= r) return tr[node].sum;
    int mid = (L + R) / 2;
    push_down(node);
    i64 res = 0;
    if (l <= mid) res = add(res, query(node << 1, L, mid, l, r));
    if (r > mid) res = add(res, query(node << 1 | 1, mid + 1, R, l, r));
    return res;
}
void modify(int node, int L, int R, int x, i64 v) {
    if (L == R) {
        tr[node].sum = v;
        return;
    }
    int mid = (L + R) / 2;
    push_down(node);
    if (x <= mid) modify(node << 1, L, mid, x, v);
    else modify(node << 1 | 1, mid + 1, R, x, v);
    push_up(node);
}
void multiply(int node, int L, int R, int l, int r, i64 v) {
    if (l <= L && R <= r) {
        tr[node].sum = mul(tr[node].sum, v);
        tr[node].tag = mul(tr[node].tag, v);
        return;
    }
    int mid = (L + R) / 2;
    push_down(node);
    if (l <= mid) multiply(node << 1, L, mid, l, r, v);
    if (r > mid) multiply(node << 1 | 1, mid + 1, R, l, r, v);
    push_up(node);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::string s;
    std::cin >> n >> q;
    std::cin >> s;
    s = ' ' + s;

    build(1, 1, n);

    while (q--) {
        int op;
        std::cin >> op;

        if (op == 1) {
            i64 l, r;
            std::cin >> l >> r;

            int x = find(1, 1, n, l), y = find(1, 1, n, r);
            if (x == y) {
                i64 v = query(1, 1, n, x, x);
                v = add(v, r - l + 1);
                modify(1, 1, n, x, v);
            } else {
                {
                    i64 v = query(1, 1, n, x, x);
                    v = add(v, query(1, 1, n, 1, x) - l + 1);
                    modify(1, 1, n, x, v);
                }
                {
                    i64 v = query(1, 1, n, y - 1, y - 1);
                    v = add(v, r - query(1, 1, n, 1, y - 1));
                    modify(1, 1, n, y, v);
                }
                if (x + 1 <= y - 1) {
                    multiply(1, 1, n, x + 1, y - 1, 2);
                }
            }
        } else {
            i64 i;
            std::cin >> i;

            int x = find(1, 1, n, i);
            std::cout << s[x] << '\n';
        }
    }
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3812kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

output:

k
h

result:

ok 2 lines

Test #3:

score: 0

Accepted

time: 0ms

memory: 3816kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #4:

score: 0

Accepted

time: 0ms

memory: 3588kb

input:

output:

k
h

result:

ok 2 lines

Test #5:

score: -100

Wrong Answer

time: 0ms

memory: 3616kb

input:

3 55
vfe
1 2 3
1 2 2
1 3 5
2 4
1 1 2
2 9
2 7
2 5
1 10 10
1 1 1
2 9
1 8 12
2 8
1 7 10
2 1
1 5 6
1 1 4
1 20 24
1 14 32
1 19 38
2 48
1 56 64
2 58
2 19
1 64 72
1 36 86
2 11
1 117 124
2 38
2 108
2 85
1 112 118
2 153
2 40
2 114
2 80
1 11 18
2 27
2 73
1 159 162
2 84
1 130 164
2 163
2 65
1 150 156
1 101 109...

output:

f
e
e
e
e
e
v
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
v

result:

wrong answer 3rd lines differ - expected: 'f', found: 'e'