oj.uz

Submission #786447

# Submission time Handle Problem Language Result Execution time Memory
786447 2023-07-18T07:55:13 Z 반딧불(#10026) Weirdtree (RMI21_weirdtree) C++17
13 / 100
 2000 ms 16672 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    pair<ll, int> tree[300002];
    ll sum[300002];

    void init(int i, int l, int r, ll *A){
        if(l==r){
            tree[i] = make_pair(A[l], -l);
            sum[i] = tree[i].first;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i] = max(tree[i*2], tree[i*2+1]);
        sum[i] = sum[i*2] + sum[i*2+1];
    }

    void update(int i, int l, int r, int x, ll v){
        if(l==r){
            tree[i] = make_pair(v, -l);
            sum[i] = tree[i].first;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = max(tree[i*2], tree[i*2+1]);
        sum[i] = sum[i*2] + sum[i*2+1];
    }

    pair<ll, int> query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return make_pair(-1, -1);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }

    ll querySum(int i, int l, int r, int s, int e){
        if(r<s || e<l) return 0;
        if(s<=l && r<=e) return sum[i];
        int m = (l+r)>>1;
        return querySum(i*2, l, m, s, e) + querySum(i*2+1, m+1, r, s, e);
    }
} tree;

int n, q;
ll arr[300002];

void initialise(int N, int Q, int h[]){
    n = N, q = Q;
    for(int i=1; i<=n; i++) arr[i] = h[i];
    tree.init(1, 1, n, arr);
}

void cut(int l, int r, int k){
    while(k--){
        int x = -tree.query(1, 1, n, l, r).second;
        if(!arr[x]) return;
        arr[x]--;
        tree.update(1, 1, n, x, arr[x]);
    }
}

void magic(int i, int x){
    arr[i] = x;
    tree.update(1, 1, n, i, x);
}

ll inspect(int l, int r){
	return tree.querySum(1, 1, n, l, r);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 42 ms 8400 KB Output is correct
4 Correct 43 ms 8388 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 5076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 5076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 16672 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 42 ms 8400 KB Output is correct
4 Correct 43 ms 8388 KB Output is correct
5 Execution timed out 2061 ms 5076 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 42 ms 8400 KB Output is correct
4 Correct 43 ms 8388 KB Output is correct
5 Execution timed out 2061 ms 5076 KB Time limit exceeded
6 Halted 0 ms 0 KB -