제출 #1219224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219224		green_gold_dog	Weirdtree (RMI21_weirdtree)	C++20	13 / 100	2096 ms	3856 KiB

weirdtree

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
#include "weirdtree.h"

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

vector<ll> na;

void initialise(int n, int q, int h[]) {
        na.resize(n);
        for (ll i = 0; i < n; i++) {
                na[i] = h[i + 1];
        }
}

void cut(int l, int r, int kq) {
        l--;
        for (ll i = 0; i < kq; i++) {
                ll mx = 0, mxi = 0;
                for (ll j = l; j < r; j++) {
                        if (assign_max(mx, na[j])) {
                                mxi = j;
                        }
                }
                if (mx > 0) {
                        na[mxi]--;
                }
        }
}

void magic(int i, int x) {
        i--;
        na[i] = x;
}

ll inspect(int l, int r) {
        l--;
        ll ans = 0;
        for (ll i = l; i < r; i++) {
                ans += na[i];
        }
        return ans;
}

#ifdef LOCAL
int main() {
    int N, Q;
    cin >> N >> Q;

    int h[N + 1];

    for (int i = 1; i <= N; ++i) cin >> h[i];

    initialise(N, Q, h);

    for (int i = 1; i <= Q; ++i) {
        int t;
        cin >> t;

        if (t == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            cut(l, r, k);
        } else if (t == 2) {
            int i, x;
            cin >> i >> x;
            magic(i, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << inspect(l, r) << '\n';
        }
    }
    return 0;
}
#endif

• 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