Submission #475543

#	Time	Username	Problem	Language	Result	Execution time	Memory
475543		lukameladze	Addk (eJOI21_addk)	C++14	100 / 100	347 ms	5024 KiB

Main

# include <bits/stdc++.h>
#define f first
#define int long long
#define s second
#define pb push_back
using namespace std;
const int N = 5e5 + 5;
int le1,ri1,pr[N],sf[N],pr1[N],a[N],q,n,ty,le,ri,m,ans,idx[N],k;
int tree[3][N + 100];
void update(int idx, int val, int id) {
     for (int i = idx; i < N; i += i&(-i)) {
          tree[id][i] += val;
     }
}
int getans(int idx, int id) {
     int pas = 0;
     for (int i = idx; i > 0; i-=i&(-i)) {
          pas += tree[id][i];
     }
     return pas;
}
int getanss(int le , int ri) {
     if (le > ri) return 0;
     return getans(ri,0) - getans(le - 1,0);
}
int getans1(int le, int ri) {
     if (le > ri) return 0;
     return getans(ri,1) - getans(le - 1,1) - (le - 1) * getanss(le,ri);
}
int getans2(int le, int ri) {
     if (le > ri) return 0;
     return getans(ri,2) - getans(le - 1, 2) - (n - ri) * getanss(le, ri);
}
main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
     cin>>n>>k;
     for (int i = 1; i <= n; i++) {
          cin>>a[i];
          update(i,a[i],0);
          update(i, i*a[i],1);
     }
     for (int i = n; i >= 1; i--){
          update(i, (n - i + 1) * a[i],2);
     }
     cin>>q;
     while (q -- ) {
          cin>>ty;
          if (ty == 2) {
               cin>>le>>ri>>m;
               if (m == 1) {
                    cout<<getanss(le,ri)<<endl;
                    continue;
               }
               if (2*m <= ri - le + 1) {
                    ans = m*getanss(le + m - 1,ri - m + 1);
                    ans += getans1(le, le + m - 2);
                    ans += getans2(ri - m + 2, ri);
               }
               else {
                    ans = 0;
                    ri1 = ri - m;
                    le1 = le + m;
              
                    ans += getans1(le,ri1);
                    ans += getans2(le1, ri);
                    ri1++; le1--;
                    ans += (ri1 - le + 1) * getanss(ri1,le1);
               }
               cout<<ans<<endl;
               continue;
          }
          for (int i = 1; i <= k; i++) {
               cin>>idx[i];
          }
          idx[k + 1] = idx[1];
          int numb = a[idx[1]];
          for (int i = 1; i <= k; i++) {
               int idxx = idx[i];
               int idxx1= idx[i+1];
               update(idxx, -a[idxx] + a[idxx1],0);
               update(idxx, idxx * (-a[idxx] + a[idxx1]),1);
               update(idxx, (n - idxx + 1) * (-a[idxx] + a[idxx1]), 2);
          }
          idx[k + 1] = idx[1];
          for (int i = 1; i <= k; i++) {
          	if (i != k)
               a[idx[i]] = a[idx[i + 1]];
                else a[idx[i]] = numb;
          }
     } 
}

Compilation message (stderr)

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

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