Submission #754942

#TimeUsernameProblemLanguageResultExecution timeMemory
754942pccFire (JOI20_ho_t5)C++14
14 / 100
735 ms103348 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define fs first #define sc second #define int ll const ll mxn = 4e5+10; struct Seg{ pll segtree[mxn*4]; Seg(){ for(auto &i:segtree)i = {0,0}; } void modify(int now,int l,int r,int s,int e,ll v){ if(l>=s&&e>=r){ segtree[now].sc += v; return; } int mid = (l+r)>>1; if(mid>=s)modify(now*2+1,l,mid,s,e,v); if(mid<e)modify(now*2+2,mid+1,r,s,e,v); segtree[now].fs = segtree[now*2+1].fs+segtree[now*2+1].sc*(mid-l+1)+segtree[now*2+2].fs+segtree[now*2+2].sc*(r-mid); } ll getval(int now,int l,int r,int s,int e){ if(l>=s&&e>=r){ return segtree[now].fs+segtree[now].sc*(r-l+1); } int mid = (l+r)>>1; if(mid>=e)return getval(now*2+1,l,mid,s,e)+segtree[now].sc*(min(e,r)-max(s,l)+1); else if(mid<s)return getval(now*2+2,mid+1,r,s,e)+segtree[now].sc*(min(e,r)-max(s,l)+1); else return getval(now*2+1,l,mid,s,e)+getval(now*2+2,mid+1,r,s,e)+segtree[now].sc*(min(e,r)-max(s,l)+1); } }; Seg seg1,seg2; vector<pll> op[mxn]; ll arr[mxn]; ll n,q; vector<tuple<ll,ll,ll>> req[mxn]; pll range[mxn]; ll ans[mxn]; ll sh = mxn>>1; void addtri(int r,int c,ll val){ op[c].push_back({r,val}); } void add(int now,int h,int w){ //cout<<now<<":"<<h<<' '<<w<<endl; addtri(now,0,arr[now]); addtri(now,h,-arr[now]); addtri(now+w,w,-arr[now]); addtri(now+w,h+w,arr[now]); return; } int32_t main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>q; for(int i = 1;i<=n;i++){ cin>>arr[i]; } for(int i = 1;i<=q;i++){ ll t,l,r; cin>>t>>l>>r; req[t].push_back(make_tuple(1LL*i,l,r)); } arr[0] = arr[n+1] = 1e18; deque<int> dq; dq.push_back(0); for(int i = 1;i<=n;i++){ while(arr[dq.back()]<arr[i])dq.pop_back(); range[i].fs = dq.back(); dq.push_back(i); } dq.clear(); dq.push_back(n+1); for(int i = n;i>=1;i--){ while(arr[dq.back()]<arr[i])dq.pop_back(); range[i].sc = dq.back(); dq.push_back(i); //cout<<i<<":"<<range[i].fs<<' '<<range[i].sc<<'\n'; } for(int i = 1;i<=n;i++){ if(range[i].fs == 0)range[i].fs = n+1; else range[i].fs = i-range[i].fs; range[i].sc = range[i].sc-i; add(i,range[i].fs,range[i].sc); } for(int i = 0;i<=n;i++){ for(auto &j:op[i]){ seg1.modify(0,1,mxn,j.fs,mxn,j.sc); seg2.modify(0,1,mxn,sh+j.fs+1,mxn,-j.sc); } for(auto &j:req[i]){ ans[get<0>(j)] = seg1.getval(0,1,mxn,get<1>(j),get<2>(j))+seg2.getval(0,1,mxn,sh+get<1>(j),sh+get<2>(j)); } /* for(int i = 1;i<=n;i++)cout<<seg1.getval(0,1,mxn,i,i)<<' ';cout<<endl; for(int i = 1;i<=n;i++)cout<<seg2.getval(0,1,mxn,sh+i,sh+i)<<' ';cout<<endl; */ sh--; } for(int i = 1;i<=q;i++)cout<<ans[i]<<'\n'; return 0; }
#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...