Submission #1221728

#TimeUsernameProblemLanguageResultExecution timeMemory
1221728Robert_juniorAddk (eJOI21_addk)C++20
100 / 100
80 ms4936 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(), x.end() #define ins insert #define pb push_back #define F first #define S second const int N = 1e6+4, M = 5e5 + 7; const int mod = 1e9 + 7; int a[N], pf[N], pf1[N], sf[N], t[N][3]; int n, k, q; void upd(int idx, int j, int x){ for(; idx <= n; idx |= (idx + 1)){ t[idx][j] += x; } } int get(int r, int j){ int res = 0; for(; r > 0; r = (r & (r + 1)) - 1){ res += t[r][j]; } return res; } int get(int l, int r, int j){ if(l > r) return 0; return get(r, j) - get(l - 1, j); } void solve(){ cin>>n>>k; int a[n + 1]; for(int i = 1; i <= n; i++){ cin>>a[i]; upd(i, 0, a[i]); upd(i, 1, a[i] * i); upd(i, 2, a[i] * (n - i + 1)); } cin>>q; while(q--){ int f; cin>>f; if(f == 1){ vector<int>v, v1; for(int i = 0; i < k; i++){ int x; cin>>x; v.pb(x); v1.pb(a[x]); } for(int i = 0; i < k; i++){ upd(v[i], 0, -a[v[i]]); upd(v[i], 1, -(a[v[i]] * v[i])); upd(v[i], 2, -(a[v[i]]) * (n - v[i] + 1)); a[v[i]] = v1[(i + 1) % k]; upd(v[i], 0, a[v[i]]); upd(v[i], 1, (a[v[i]] * v[i])); upd(v[i], 2, (a[v[i]]) * (n - v[i] + 1)); } } else{ int sum = 0, l, r, m, l1, r1; cin>>l>>r>>m; int len = r - l + 1; int mid = min(m, (r - l + 1) - m + 1); if(mid * 2 <= len){ //sum += (pf[r - mid] - pf[l + mid - 1]) * mid; sum += get(l + mid, r - mid, 0) * mid; //sum += (pf1[l + mid - 1] - pf1[l - 1]) - (pf[l + mid - 1] - pf[l - 1]) * (l - 1); sum += get(l, l + mid - 1, 1) - get(l, l + mid - 1, 0) * (l - 1); //sum += (sf[r - mid + 1] - sf[r + 1]) - (pf[r] - pf[r - mid]) * (n - r); sum += get(r - mid + 1, r, 2) - get(r - mid + 1, r, 0) * (n - r); } else{ for(int i = l; i <= r; i++){ sum += a[i] * min({i - l + 1, r - i + 1, mid}); } } cout<<sum<<'\n'; } } } main(){ ios_base :: sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin>>t; for(int i = 1; i <= t; i++){ //cout<<"Case "<<i<<": "; solve(); } }

Compilation message (stderr)

Main.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...