제출 #515931

#제출 시각아이디문제언어결과실행 시간메모리
515931Jarif_RahmanFire (JOI20_ho_t5)C++17
100 / 100
412 ms33356 KiB
#include <bits/stdc++.h> #define pb push_back #define f first #define sc second using namespace std; typedef long long int ll; typedef string str; struct BIT{ int n; vector<ll> sm; BIT(int _n){ n = _n; sm.resize(n); } void add(int in, ll x){ in++; while(in <= n) sm[in-1]+=x, in+=in&-in; } ll sum(int in){ in++; ll s = 0; while(in >= 1) s+=sm[in-1], in-=in&-in; return s; } ll sum(int l, int r){ return sum(r)-(l == 0? 0:sum(l-1)); } void assign(int in, ll x){ add(in, x-sum(in, in)); } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; vector<ll> s(n); for(ll &x: s) cin >> x; vector<int> prev(n, -1); stack<int> st; for(int i = n-1; i >= 0; i--){ while(!st.empty() && s[i] > s[st.top()]) prev[st.top()] = i, st.pop(); st.push(i); } while(!st.empty()) st.pop(); vector<vector<int>> end(n+1); vector<vector<pair<int, int>>> chng(n+1); for(int i = 0; i < n; i++){ while(!st.empty() && s[st.top()] <= s[i]){ int x = st.top(); st.pop(); end[i-x-1].pb(x); if(prev[x] == -1) continue; if(s[prev[x]] <= s[i]) continue; chng[i-prev[x]-1].pb({prev[x], i}); } st.push(i); } while(!st.empty()) end[n-st.top()-1].pb(st.top()), st.pop(); vector<vector<array<int, 3>>> queries(n); for(int i = 0; i < q; i++){ int t, l, r; cin >> t >> l >> r; t--, l--, r--; queries[t].pb({l, r, i}); } vector<ll> ans(q, 0); BIT ss(n); BIT s1(n), s2(n), s3(n); for(int i = 0; i < n; i++) ss.add(i, s[i]); for(int i = 0; i+1 < n; i++){ s1.assign(i, max(0LL, s[i]-s[i+1])); s2.assign(i, max(0LL, s[i]-s[i+1])*i); s3.assign(i, max(0LL, s[i]-s[i+1])*(n-1-i)); } for(int t = 1; t <= n; t++){ for(int in: end[t-1]){ if(in != n-1) for(int i = in+1; i <= in+t-1; i++) ss.add(i, s1.sum(in, in)); s1.assign(in, 0); s2.assign(in, 0); s3.assign(in, 0); } for(auto [in, nxt]: chng[t-1]){ ll x = s1.sum(in, in)-(s[in]-s[nxt]); for(int i = in+1; i < nxt; i++) ss.add(i, x); s1.assign(in, s[in]-s[nxt]); s2.assign(in, (s[in]-s[nxt])*in); s3.assign(in, (s[in]-s[nxt])*(n-1-in)); } for(auto [l, r, in]: queries[t-1]){ ans[in]+=ss.sum(l, r); int mx, a, b; if(t <= r-l+1){ mx = t; a = l, b = r-mx+1; a--, b--; a = max(a, 0); } else{ mx = r-l+1; a = r-t+1, b = l; a--, b--; a = max(a, 0); } ans[in]+=s1.sum(a, b)*mx; if(mx != 1){ int aa = max(0, a-mx+1); ll c = s2.sum(aa, a-1)+(s1.sum(aa, a-1)*(mx-a)); ans[in]+=c; int bb = min(n-1, b+mx-1); c = s3.sum(b+1, bb)+(s1.sum(b+1, bb)*(mx-(n-1-b))); ans[in]+=c; } } } for(ll x: ans) cout << x << "\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...