oj.uz

Submission #785937

# Submission time Handle Problem Language Result Execution time Memory
785937 2023-07-17T19:29:52 Z Bula Addk (eJOI21_addk) C++17
100 / 100
 1268 ms 9568 KB 
#include <bits/stdc++.h>
using namespace std;
 	
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define s second
#define pi pair<int,int>
#define pii pair< pair<int,int> , pair<int,int> >  
#define int ll
const ll mod=1e9+7,N=1e5+1;
vector<int> a(N),t(4*N);

int combine(int l,int r){
	return l+r;
}


void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        t[v]=combine(t[v*2],t[v*2+1]);
    }
}

int get(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && r == tr) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return combine(get(v*2, tl, tm, l, min(r, tm)),get(v*2+1, tm+1, tr, max(l, tm+1), r));
}

void up(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            up(v*2, tl, tm, pos, new_val);
        else
            up(v*2+1, tm+1, tr, pos, new_val);
		t[v] = combine(t[v*2],t[v*2+1]);
    }
}

 
main(){
 
    int tt=1;//cin>>tt;
    while(tt--){
    	int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        build(1,1,n);
        int q;
        cin>>q;
        while(q--){
            int x;
            cin>>x;
            if(x==1){
                vector<int> p(k+1),p1(k+1);
                for(int i=1;i<=k;i++) cin>>p[i];
                for(int i=1;i<=k;i++){
                    int j=i+1;
                    if(i==k) j=1;
                    p1[i]=a[p[j]];
                }
                for(int i=1;i<=k;i++){
                    up(1, 1, n, p[i], p1[i]);
                    a[p[i]]=p1[i];
                }
            }else{
                int l,r,m;
                cin>>l>>r>>m;
                int s=get(1,1,n,l,r),ans=s*m,l1=l,r1=r;
                for(int i=m-1;i>=1;i--){
                    ans-=i*a[l1];
                    ans-=i*a[r1];
                    l1++;
                    r1--;
                }
                cout<<ans<<endl;
            }
        }
    }
}

Compilation message

Main.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main(){
      | ^~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 4 ms 4236 KB Output is correct
3 Correct 6 ms 4244 KB Output is correct
4 Correct 10 ms 4320 KB Output is correct
5 Correct 14 ms 4344 KB Output is correct
6 Correct 18 ms 4376 KB Output is correct
7 Correct 23 ms 4308 KB Output is correct
8 Correct 30 ms 4472 KB Output is correct
9 Correct 46 ms 4548 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 4892 KB Output is correct
2 Correct 287 ms 5352 KB Output is correct
3 Correct 461 ms 5752 KB Output is correct
4 Correct 871 ms 6948 KB Output is correct
5 Correct 1243 ms 8148 KB Output is correct
6 Correct 1168 ms 8032 KB Output is correct
7 Correct 1012 ms 7872 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 6740 KB Output is correct
2 Correct 882 ms 7696 KB Output is correct
3 Correct 343 ms 9568 KB Output is correct
4 Correct 1268 ms 8384 KB Output is correct