Submission #733569

#TimeUsernameProblemLanguageResultExecution timeMemory
733569pccFire (JOI20_ho_t5)C++14
1 / 100
91 ms10828 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define pll pair<ll,ll> #define fs first #define sc second const int mxn = 2e5+10; int arr[mxn]; int brr[mxn]; ll bit[mxn]; int n,q; void modify(int p,ll v){ for(;p<mxn;p+=p&-p)bit[p] += v; return; } ll getval(int s,int e){ ll re = 0; for(;e>0;e-= e&-e)re += bit[e]; s--; for(;s>0;s -= s&-s)re -= bit[s]; return re; } void calc(){ int l,r,t; cin>>t>>l>>r; int tmp[n+1]; for(int i = 1;i<=n;i++)tmp[i] = arr[i]; while(t--){ for(int i = n-1;i>=1;i--){ tmp[i+1] = max(tmp[i+1],tmp[i]); } } ll total = 0; for(int i = l;i<=r;i++)total += tmp[i]; cout<<total<<'\n'; return; } void solve(){ cin>>n>>q; for(int i = 1;i<=n;i++)cin>>arr[i],brr[i] = arr[i]; /* */ if(n<=200&&q<=200){ while(q--)calc(); return; } ll t = 0; pll req[q]; for(auto &i:req){ cin>>t; cin>>i.fs>>i.sc; } ll p = 0; for(int i = 1;i<=n;i++){ if(p<=i)p = i; while(p<n&&p+1-i<=t&&arr[p]<=arr[i]&&arr[p+1]<=arr[i]){ p++; brr[p] = arr[i]; } //cout<<i<<":"<<p<<endl; } for(int i = 1;i<=n;i++)modify(i,brr[i]);//cout<<brr[i]<<' ';cout<<endl; for(auto &i:req){ cout<<getval(i.fs,i.sc)<<'\n'; } return; } int32_t main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; while(t--)solve(); }
#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...