QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#820889	#9791. Intrusive Donkey	kkzyr	WA	0ms	3600kb	C++17	2.4kb	2024-12-19 09:24:09	2024-12-19 09:24:14

Judging History

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

[2024-12-19 09:24:14]
评测

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

查看

[2024-12-19 09:24:09]
提交

answer

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

const int MAX_N = 2e5 + 5;

int n, q;
string s;

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];

long long the_sum;

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;
        }
    }
    the_sum = curr_sum + tree[tree_node].size;
    return tree_node;
}

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

int main(){
    cin >> n >> q >> s;
    size_tree = 1;
    while (size_tree < n){
        size_tree *= 2;
    }
    for (int i = 1;i <= size_tree;i++){
        tree[size_tree - 1 + i] = {i, i};
        if (i <= n){
            tree[size_tree - 1 + i].size = 1;
        }
    }
    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) - (size_tree - 1) - 1] << '\n';
        }
    }
    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3476kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

output:

k
h

result:

ok 2 lines

Test #3:

score: 0

Accepted

time: 0ms

memory: 3512kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #4:

score: 0

Accepted

time: 0ms

memory: 3472kb

input:

output:

k
h

result:

ok 2 lines

Test #5:

score: -100

Wrong Answer

time: 0ms

memory: 3596kb

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:

result:

wrong answer 2nd lines differ - expected: 'e', found: ''