제출 #940962

#제출 시각아이디문제언어결과실행 시간메모리
940962LittleOrangeFire (JOI20_ho_t5)C++17
7 / 100
1050 ms20048 KiB
#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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...