Submission #475466

#TimeUsernameProblemLanguageResultExecution timeMemory
475466akobiAddk (eJOI21_addk)C++98
92 / 100
571 ms6680 KiB
#include <bits/stdc++.h> #define ll long long #define mp make_pair #define F first #define S second #define pb push_back using namespace std; ll n,f1[400005],f2[400005],a[100005]; void upd1(ll id,ll L,ll R,ll f,ll d) { if (f<L || R<f) return; if (L==R) { f1[id]=d; f2[id]=d*(f+1); return; } upd1( 2*id , L ,(L+R)/2,f,d); upd1(2*id+1,(L+R)/2+1, R ,f,d); f1[id]=f1[2*id]+f1[2*id+1]; f2[id]=f2[2*id]+f2[2*id+1]; return; } void upd(vector< pair<ll,ll> > u) { ll temp=u[0].F; for (ll i=0; i<u.size()-1; i++) a[u[i].S]=u[i+1].F; a[u.size()-1]=temp; for (ll i=0; i<u.size(); i++) upd1(1,0,n-1,u[i].S,u[(i+1)%u.size()].F); return; } ll get1(ll id,ll L,ll R,ll l,ll r) { if (R<l || r<L) return 0; if (l<=L && R<=r) return f1[id]; return get1( 2*id , L ,(L+R)/2,l,r)+ get1(2*id+1,(L+R)/2+1, R ,l,r); } ll get2(ll id,ll L,ll R,ll l,ll r) { if (R<l || r<L) return 0; if (l<=L && R<=r) return f2[id]; return get2( 2*id , L ,(L+R)/2,l,r)+ get2(2*id+1,(L+R)/2+1, R ,l,r); } ll get(ll L,ll R,ll m) { if (m==1) return get1(1,0,n-1,L,R); ll ans=0; ans+=get2(1,0,n-1,L,min(L+m-1,R-m+1)-1); ans-=get1(1,0,n-1,L,min(L+m-1,R-m+1)-1)*L; ans+=get1(1,0,n-1,min(L+m-1,R-m+1),max(L+m-1,R-m+1)) *(min(L+m-1,R-m+1)-L+1); ans-=get2(1,0,n-1,max(L+m-1,R-m+1)+1,R); ans+=get1(1,0,n-1,max(L+m-1,R-m+1)+1,R)*(R+2); return ans; } ll k,q,qt,l,r,m; vector< pair<ll,ll> > u; int main() { cin>>n>>k; u.pb(mp(0,0)); for (ll i=0; i<n; i++) { cin>>a[i]; u[0]=mp(a[i],i); upd(u); } for (ll i=1; i<k; i++) u.pb(mp(0,0)); cin>>q; while (q--) { cin>>qt; if (qt==1) { for (ll i=0; i<k; i++) { cin>>u[i].S; u[i].S--; u[i].F=a[u[i].S]; } upd(u); } else { cin>>l>>r>>m; cout<<get(l-1,r-1,m)<<endl; } } return 0; }

Compilation message (stderr)

Main.cpp: In function 'void upd(std::vector<std::pair<long long int, long long int> >)':
Main.cpp:28:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (ll i=0; i<u.size()-1; i++)
      |               ~^~~~~~~~~~~
Main.cpp:31:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (ll i=0; i<u.size(); i++)
      |               ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...