oj.uz

Submission #475519

# Submission time Handle Problem Language Result Execution time Memory
475519 2021-09-22T18:18:02 Z lukameladze Addk (eJOI21_addk) C++14
92 / 100
 346 ms 7428 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];
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);
  //   return (sf[le] - sf[ri + 1] - (n - ri) * getans(le,ri));
}
main() {
     int k;
     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];
          }
          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);
          }
          int idxx = idx[k]; int idxx1 = idx[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++) {
               a[idx[i]] = a[idx[i + 1]];
          }
     } 
}

Compilation message

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

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 7 ms 460 KB Output is correct
4 Correct 10 ms 588 KB Output is correct
5 Correct 17 ms 588 KB Output is correct
6 Correct 21 ms 716 KB Output is correct
7 Correct 19 ms 796 KB Output is correct
8 Correct 20 ms 716 KB Output is correct
9 Correct 41 ms 924 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 1520 KB Output is correct
2 Correct 132 ms 2172 KB Output is correct
3 Correct 118 ms 3032 KB Output is correct
4 Correct 346 ms 4620 KB Output is correct
5 Correct 319 ms 7428 KB Output is correct
6 Correct 287 ms 7252 KB Output is correct
7 Correct 337 ms 7180 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 210 ms 4364 KB Output isn't correct
2 Halted 0 ms 0 KB -