제출 #1131782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131782		antonn	Fire (JOI20_ho_t5)	C++20	1 / 100	1095 ms	2808 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];

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];
    
    vector<int> lft(n + 1), rgh(n + 1);
    vector<int> stk;
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && a[i] >= a[stk.back()]) stk.pop_back();
        if (stk.empty()) lft[i] = -1e9;
        if (!stk.empty()) lft[i] = stk.back() + 1;
        stk.push_back(i);
    }
    stk.clear();
    for (int i = n; i >= 1; --i) {
        while (!stk.empty() && a[i] >= a[stk.back()]) stk.pop_back();
        if (stk.empty()) rgh[i] = +1e9;
        if (!stk.empty()) rgh[i] = stk.back() - 1;
        stk.push_back(i);
    }
    
    for (int i = 1; i <= q; ++i) {
        int t, l, r; cin >> t >> l >> r;
        ll ans = 0;
        for (int j = 1; j <= n; ++j) {
            int L = max({lft[j] + t, l, j}); 
            int R = min({j + t, r, rgh[j]});
            if (L <= R) ans += (ll) (R - L + 1) * a[j];
        }
        cout << ans << "\n";
    }
}

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