제출 #1146715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146715		koukirocks	Fire (JOI20_ho_t5)	C++20	6 / 100	58 ms	7240 KiB

ho_t5

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int INF=0x3f3f3f3f;
const ll oo=0x3f3f3f3f3f3f3f3f;
template<class T>
using vvector = vector<vector<T>>;

int main() {
    speed;
    int n,q;
    cin>>n>>q;
    vector<ll> s(n+1);
    for (int i=1;i<=n;i++) {
        cin>>s[i];
    }
    deque<pii> Q;
    vector<pair<pii,int>> qry(q+1);
    for (int i=1;i<=q;i++) {
        cin>>qry[i].S>>qry[i].F.F>>qry[i].F.S;
    }
    for (int i=1;i<=n;i++) {
        while (!Q.empty() and Q.back().F<=s[i]) Q.pop_back();
        Q.push_back({s[i],i});
        if (Q.front().S<i-qry[1].S) Q.pop_front();
        s[i]=Q.front().F;
    }
    for (int i=1;i<=n;i++) s[i]+=s[i-1];
    for (int i=1;i<=q;i++) {
        cout<<s[qry[i].F.S]-s[qry[i].F.F-1]<<"\n";
    }
}

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