QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#820858	#9791. Intrusive Donkey	kkzyr	WA	0ms	5700kb	C++17	2.7kb	2024-12-19 08:29:24	2024-12-19 08:29:24

Judging History

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

[2024-12-19 08:29:24]
评测

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

查看

[2024-12-19 08:29:24]
提交

answer

#include <iostream>
#include <string>
using namespace std;

const int MAX_N = 2e5 + 5;

int n, q;
string s;

int num_ranges;
int ranges[MAX_N];

struct node{
    int left, right;
    long long size;
};
node merge(node x, node y){
    return {x.left, y.right, x.size + y.size};
}

int size_tree;
node tree[4 * MAX_N];

int find(long long index){
    long long curr_sum = 0;
    int tree_node = 1;
    while (tree_node < size_tree){
        if (curr_sum + tree[2 * tree_node].size + 1 <= index){
            curr_sum += tree[2 * tree_node].size;
            tree_node = 2 * tree_node + 1;
        }
        else{
            tree_node *= 2;
        }
    }
    return tree_node - (size_tree - 1);
}

void double_range(long long l, long long r){
    int leftmost = find(l);
    int rightmost = find(r);
    if (leftmost == rightmost){
        tree[size_tree - 1 + leftmost].size += r - l + 1;
        leftmost += size_tree - 1;
        leftmost /= 2;
        while (leftmost >= 1){
            tree[leftmost] = merge(tree[2 * leftmost], tree[2 * leftmost + 1]);
            leftmost /= 2;
        }
    }
    else{
        tree[size_tree - 1 + leftmost].size += tree[size_tree - 1 + leftmost].right - l + 1;
        tree[size_tree - 1 + rightmost].size += r - tree[size_tree - 1 + rightmost].left + 1;
        for (int i = leftmost + 1;i <= rightmost - 1;i++){
            tree[size_tree - 1 + i].size *= 2;
        }
        leftmost += size_tree - 1, rightmost += size_tree - 1;
        while (leftmost >= 1){
            leftmost /= 2, rightmost /= 2;
            for (int i = leftmost;i <= rightmost;i++){
                tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
            }
        }
    }
}

int main(){
    cin >> n >> q >> s;
    int pos = 0;
    while (pos < s.size()){
        int original = pos;
        while (pos < s.size() and s[pos] == s[original]){
            pos++;
        }
        num_ranges++;
        ranges[num_ranges] = pos - original;
    }
    size_tree = 1;
    while (size_tree < num_ranges){
        size_tree *= 2;
    }
    for (int i = 1;i <= size_tree;i++){
        tree[size_tree - 1 + i] = {i, i};
        if (i <= num_ranges){
            tree[size_tree - 1 + i].size = ranges[i];
        }
    }
    for (int i = size_tree - 1;i >= 1;i--){
        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }
    for (int i = 1;i <= q;i++){
        int type;
        cin >> type;
        if (type == 1){
            long long l, r;
            cin >> l >> r;
            double_range(l, r);
        }
        else{
            long long index;
            cin >> index;
            cout << s[find(index) - 1] << '\n';
        }
    }
    return 0;
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 5540kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 5700kb

input:

output:

k
h

result:

ok 2 lines

Test #3:

score: 0

Accepted

time: 0ms

memory: 3568kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #4:

score: 0

Accepted

time: 0ms

memory: 5700kb

input:

output:

k
h

result:

ok 2 lines

Test #5:

score: -100

Wrong Answer

time: 0ms

memory: 3588kb

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
f
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'