Submission #785937

#	Time	Username	Problem	Language	Result	Execution time	Memory
785937		Bula	Addk (eJOI21_addk)	C++17	100 / 100	1268 ms	9568 KiB

Main

#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 (stderr)

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

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8