Submission #733583

#TimeUsernameProblemLanguageResultExecution timeMemory
733583pccFire (JOI20_ho_t5)C++14
7 / 100
208 ms23372 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]; //for(int i =1;i<=n;i++)cout<<tmp[i]<<' ';cout<<endl; 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; multiset<int> st; for(int i = 1;i<=n;i++){ st.insert(arr[i]); if(st.size()>t+1)st.erase(st.find(arr[i-t-1])); brr[i] = *st.rbegin(); } for(int i = 1;i<=n;i++)modify(i,brr[i]);//cout<<brr[i]<<' ';cout<<endl; //for(int i = 1;i<=n;i++)cout<<brr[i]<<' ';cout<<endl; for(auto &i:req){ cout<<getval(i.fs,i.sc)<<'\n'; } return; } /* 14 1 326908579 2008726166 6331162 13968167 1029427745 1923822745 2842230206 1213122301 2675719680 327392163 13456315 65956481 1342328178 2252328063 2 1 14 */ int32_t main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; while(t--)solve(); }

Compilation message (stderr)

ho_t5.cpp: In function 'void solve()':
ho_t5.cpp:65:15: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   65 |   if(st.size()>t+1)st.erase(st.find(arr[i-t-1]));
      |      ~~~~~~~~~^~~~
ho_t5.cpp:61:5: warning: unused variable 'p' [-Wunused-variable]
   61 |  ll p = 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...