Submission #1131770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131770		antonn	Fire (JOI20_ho_t5)	C++20	8 / 100	1096 ms	17108 KiB

ho_t5

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 2e5+7;
const int L = 20;

int a[N], t[L][N], lg[N]; 

int get_max(int l, int r) {
    int p = lg[r - l + 1];
    return max(t[p][l], t[p][r - (1 << p) + 1]);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    for (int i = 1; i <= n; ++i) t[0][i] = a[i];
    for (int h = 1; h < L; ++h) {
        for (int i = 1; i + (1 << h) - 1 <= n; ++i) {
            t[h][i] = max(t[h - 1][i], t[h - 1][i + (1 << (h - 1))]);
        }
    }
    for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1; 
    
    for (int i = 1; i <= q; ++i) {
        int t, l, r; cin >> t >> l >> r;
        ll ans = 0;
        for (int j = l; j <= r; ++j) {
            ans += get_max(max(1, j - t), j);
        }
        cout << ans << "\n";
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80