제출 #940962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
940962		LittleOrange	Fire (JOI20_ho_t5)	C++17	7 / 100	1050 ms	20048 KiB

ho_t5

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
    ll t,l,r,i;
    bool operator<(const obj &o) const{
        return t<o.t;
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,q;
    cin >> n >> q;
    vector<ll> a(n);
    for(ll &i : a) cin >> i;
    vector<obj> qs(q);
    for(ll i = 0;i<q;i++){
        qs[i].i = i;
        cin >> qs[i].t >> qs[i].l >> qs[i].r;
    }
    sort(qs.begin(),qs.end());
    vector<ll> ans(q);
    vector<ll> b(n+1,0);
    for(ll i = 0;i<n;i++) b[i+1] = a[i]+b[i];
    ll t = 0;
    for(obj o : qs){
        ll dt = o.t-t;
        if(dt){
            deque<pair<ll,ll>> q;
            for(ll i = 0;i<n;i++){
                while(q.size()&&q.front().second<i-dt) q.pop_front();
                while(q.size()&&q.back().first<=a[i]) q.pop_back();
                q.push_back({a[i],i});
                a[i] = q.front().first;
            }
            for(ll i = 0;i<n;i++) b[i+1] = a[i]+b[i];
            t = o.t;
        }
        //for(ll i = 0;i<n;i++) cout << a[i] << " \n"[i+1==n];
        ans[o.i] = b[o.r]-b[o.l-1];
    }
    for(ll i : ans) cout << i << "\n";
}

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