oj.uz

Submission #475543

# Submission time Handle Problem Language Result Execution time Memory
475543 2021-09-22T19:48:35 Z lukameladze Addk (eJOI21_addk) C++14
100 / 100
 347 ms 5024 KB 
# 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

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

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 6 ms 496 KB Output is correct
4 Correct 9 ms 460 KB Output is correct
5 Correct 11 ms 588 KB Output is correct
6 Correct 14 ms 624 KB Output is correct
7 Correct 16 ms 660 KB Output is correct
8 Correct 18 ms 700 KB Output is correct
9 Correct 30 ms 816 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1224 KB Output is correct
2 Correct 86 ms 1728 KB Output is correct
3 Correct 118 ms 2352 KB Output is correct
4 Correct 212 ms 3544 KB Output is correct
5 Correct 291 ms 5024 KB Output is correct
6 Correct 268 ms 4936 KB Output is correct
7 Correct 262 ms 4820 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 2536 KB Output is correct
2 Correct 257 ms 3932 KB Output is correct
3 Correct 347 ms 4204 KB Output is correct
4 Correct 299 ms 4932 KB Output is correct