oj.uz

Submission #744048

# Submission time Handle Problem Language Result Execution time Memory
744048 2023-05-18T07:40:09 Z siewjh Weirdtree (RMI21_weirdtree) C++17
21 / 100
 2000 ms 42560 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll height[1005];
int nums;

struct node{
    int s, e, m; pair<ll, int> val; ll sum;
    node *l, *r;
    node(int _s, int _e){
        s = _s, e = _e, m = (s + e) >> 1, val = {0, -s}, sum = 0;
        if (s != e){
            l = new node(s, m);
            r = new node(m + 1, e);
        }
    }
    void update(int p, ll v){
        if (s == e){
            val.first = v;
            sum = v;
            return;
        }
        else if (p <= m) l->update(p, v);
        else r->update(p, v);
        val = max(l->val, r->val);
        sum = l->sum + r->sum;
    }
    pair<ll, int> qmax(int x, int y){
        if (x == s && y == e) return val;
        else if (y <= m) return l->qmax(x, y);
        else if (x > m) return r->qmax(x, y);
        else return max(l->qmax(x, m), r->qmax(m + 1, y));
    }
    ll qsum(int x, int y){
        if (x == s && y == e) return sum;
        else if (y <= m) return l->qsum(x, y);
        else if (x > m) return r->qsum(x, y);
        else return l->qsum(x, m)+ r->qsum(m + 1, y);
    }
}*root;

void initialise(int N, int Q, int h[]) {
    nums = N;
    if (nums <= 1000){
        for (int i = 1; i <= N; i++) height[i] = h[i];
    }
    else{
        root = new node(1, N);
        for (int i = 1; i <= N; i++) root->update(i, h[i]);
    }
}
void cut(int l, int r, int k) {
    if (nums <= 1000){
        ll lh = 0, rh = 1e9 + 5, ans = 0;
        while (lh <= rh){
            ll mh = (lh + rh) >> 1, sum = 0;
            for (int i = l; i <= r; i++)
                if (height[i] > mh)
                    sum += height[i] - mh;
            if (sum >= k){
                ans = mh;
                lh = mh + 1;
            }
            else rh = mh - 1;
        }
        ll sum = 0;
        for (int i = l; i <= r; i++)
            if (height[i] > ans)
                sum += height[i] - ans;
        if (sum >= k){
            ll rem = sum - k;
            for (int i = r; i >= l; i--)
                if (height[i] > ans){
                    if (rem > 0){
                        height[i] = ans + 1;
                        rem--;
                    }
                    else height[i] = ans;
                }
        }
        else{
            for (int i = l; i <= r; i++) height[i] = 0;
        }
    }
    else{
        for (int i = 0; i < k; i++){
            auto res = root->qmax(l, r);
            if (res.first == 0) break;
            root->update(-res.second, res.first - 1);
        }
    }
}
void magic(int i, int x) {
    if (nums <= 1000) height[i] = x;
	else root->update(i, x);
}
ll inspect(int l, int r) {
    if (nums <= 1000){
        ll sum = 0;
        for (int i = l; i <= r; i++) sum += height[i];
        return sum;
    }
	return root->qsum(l, r);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 66 ms 10592 KB Output is correct
4 Correct 70 ms 10428 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 457 ms 41436 KB Output is correct
4 Correct 418 ms 42560 KB Output is correct
5 Correct 465 ms 41164 KB Output is correct
6 Correct 403 ms 41764 KB Output is correct
7 Execution timed out 2085 ms 10708 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 66 ms 10592 KB Output is correct
4 Correct 70 ms 10428 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Execution timed out 2085 ms 10708 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 66 ms 10592 KB Output is correct
4 Correct 70 ms 10428 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 457 ms 41436 KB Output is correct
8 Correct 418 ms 42560 KB Output is correct
9 Correct 465 ms 41164 KB Output is correct
10 Correct 403 ms 41764 KB Output is correct
11 Execution timed out 2085 ms 10708 KB Time limit exceeded
12 Halted 0 ms 0 KB -