oj.uz

Submission #476962

# Submission time Handle Problem Language Result Execution time Memory
476962 2021-09-29T12:05:54 Z David_M Addk (eJOI21_addk) C++14
100 / 100
 236 ms 10464 KB 
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define FF first.first
#define FS first.second
#define pb push_back
using namespace std;
const ll N=1000006, INF=1e18, P=998244353;

ll q=1, n, m, x, y, z, l, r, k, t, a[N], b[N], f[N], ans, o, u, Ans[N];
pair<ll, ll> T[N];

void upd(int x, ll val, int v=1, int L=1, int R=n){
    int M=L+R>>1;
    if(L==R){T[v]={val,val*x};return;}
    if(x<=M)upd(x, val, v<<1, L, M);
    else    upd(x, val, v<<1|1, M+1, R);
    T[v]={T[v<<1].F+T[v<<1|1].F, T[v<<1].S+T[v<<1|1].S};
}

ll get(int l, int r, int v=1, int L=1, int R=n){
    if(R<l || L>r)return 0;
    if(L>=l && R<=r)return T[v].S-T[v].F*(l-1);
    int M=L+R>>1;
    return get(l, r, v<<1, L, M)+get(l, r, v<<1|1, M+1, R);
}



main(){ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>k;

	for (int i=1; i<=n; i++)cin>>a[i],upd(i,a[i]);
	cin>>q;
	b[k]=n+1;
	while(q--){
        cin>>t;
        if(t==1){
            for (int i=0; i<k; i++)cin>>b[i];a[n+1]=a[b[0]];
            for (int i=0; i<k; i++)a[b[i]]=a[b[i+1]],upd(b[i],a[b[i]]);
        }else{
            cin>>l>>r>>m;
            //cout<<l<<" "<<r<<'\n'<<min(r-m+2, l+m)<<" "<<r<<'\n'<<max(r-m+2, l+m)<<" "<<r<<'\n';
            cout<<get(l,r)-get(min(r-m+2, l+m),r)-get(max(r-m+2, l+m), r)<<'\n';
        }
	}


}

Compilation message

Main.cpp: In function 'void upd(int, long long int, int, int, int)':
Main.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |     int M=L+R>>1;
      |           ~^~
Main.cpp: In function 'long long int get(int, int, int, int, int)':
Main.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |     int M=L+R>>1;
      |           ~^~
Main.cpp: At global scope:
Main.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main(){ios_base::sync_with_stdio(false), cin.tie(0);
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:43:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |             for (int i=0; i<k; i++)cin>>b[i];a[n+1]=a[b[0]];
      |             ^~~
Main.cpp:43:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |             for (int i=0; i<k; i++)cin>>b[i];a[n+1]=a[b[0]];
      |                                              ^

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 7 ms 588 KB Output is correct
7 Correct 8 ms 656 KB Output is correct
8 Correct 9 ms 716 KB Output is correct
9 Correct 13 ms 972 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1712 KB Output is correct
2 Correct 43 ms 1900 KB Output is correct
3 Correct 59 ms 3244 KB Output is correct
4 Correct 110 ms 6024 KB Output is correct
5 Correct 169 ms 6724 KB Output is correct
6 Correct 150 ms 6492 KB Output is correct
7 Correct 157 ms 6556 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3176 KB Output is correct
2 Correct 162 ms 8592 KB Output is correct
3 Correct 236 ms 10464 KB Output is correct
4 Correct 177 ms 9392 KB Output is correct