Submission #760788

#	Time	Username	Problem	Language	Result	Execution time	Memory
760788		bachhoangxuan	Addk (eJOI21_addk)	C++17	100 / 100	78 ms	8780 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 1000005
#define maxk 15
int bit[3][maxn],a[maxn],n,k,q,x[maxk];
int query(int t,int x){
    int res=0;
    for(int i=x;i>=1;i-=(i&(-i))) res+=bit[t][i];
    return res;
}
void update(int t,int x,int val){
    for(int i=x;i<=n;i+=(i&(-i))) bit[t][i]+=val;
}
void up(int x,int val){
    update(0,x,val);
    update(1,x,val*x);
    update(2,x,val*(n-x+1));
}
int calc(int t,int l,int r){
    int res=query(t,r)-query(t,l-1);
    return res;
}
int qu(int l,int r,int m){
    int len=(r-l+1),t=min(len-m,m-1),res=len-2*t;
    return calc(1,l,l+t-1)-calc(0,l,l+t-1)*(l-1)+calc(2,r-t+1,r)-calc(0,r-t+1,r)*(n-r)+calc(0,l+t,r-t)*(t+1);
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin >> n >> k;
    for(int i=1;i<=n;i++){cin >> a[i];up(i,a[i]);}
    cin >> q;
    while(q--){
        int id;cin >> id;
        if(id==2){
            int l,r,m;cin >> l >> r >> m;
            cout << qu(l,r,m) << '\n';
        }
        else{
            for(int i=0;i<k;i++) cin >> x[i];
            for(int i=0;i<k;i++) up(x[i],a[x[(i+1)%k]]-a[x[i]]);
            for(int i=0;i<k-1;i++) swap(a[x[i]],a[x[i+1]]);
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'long long int qu(long long int, long long int, long long int)':
Main.cpp:25:38: warning: unused variable 'res' [-Wunused-variable]
   25 |     int len=(r-l+1),t=min(len-m,m-1),res=len-2*t;
      |                                      ^~~

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