제출 #744012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744012		siewjh	Weirdtree (RMI21_weirdtree)	C++17	13 / 100	2072 ms	46720 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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[]) {
	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) {
	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) {
	root->update(i, x);
}
ll inspect(int l, int r) {
	return root->qsum(l, r);
	return -1;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29