oj.uz

Submission #666465

# Submission time Handle Problem Language Result Execution time Memory
666465 2022-11-28T16:44:40 Z divad Addk (eJOI21_addk) C++14
100 / 100
 333 ms 9508 KB 
#include <iostream>
#include <cstring>
#define int long long
#define MAX 100002
using namespace std;
int n,k,a[MAX],asc[MAX],desc[MAX],v[MAX],x,t,m,l,r,q,c[MAX],cpy[MAX];

int query(int aib[MAX], int pos){
    int ans = 0;
    for(int i = pos; i > 0; i -= (i&-i)){
        ans += aib[i];
    }
    return ans;
}

void update(int aib[MAX], int pos, int val){
    for(int i = pos; i <= n; i += (i&-i)){
        aib[i] += val;
    }
}

int range(int aib[MAX], int x, int y){
    return query(aib, y)-query(aib, x-1);
}

signed main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
        cpy[i] = v[i];
        update(a, i, v[i]);
        update(asc, i, i*v[i]);
        update(desc, i, (n-i+1)*v[i]);
    }
    cin >> q;
    while(q--){
        cin >> t;
        if(t == 2){
            cin >> l >> r >> m;
            int len = r-l+1;
            if(m > len/2){
                m = len-m+1;
            }
            /// asc   - [l      , l+m-2  ]
            /// const - [l+m-1  , r-(m-1)]
            /// desc  - [r-(m-2), r      ]
            /// S1  = range(asc, l, l+m-2) - (l-1)*range(a, l, l+m-2)
            /// S2  = m * range(a, l+m-1, r-(m-1))
            /// S3  = range(desc, r-(m-2), r) - ( (r-(m-2))-(m-1) ) * range(a, r-(m-2), r)
            int s1 = range(asc, l, l+m-2) - (l-1)*range(a, l, l+m-2);
            int s2 = m * range(a, l+m-1, r-(m-1));
            int s3 = range(desc, r-(m-2), r) - ((n-(r-(m-2))+1)-(m-1)) * range(a, r-(m-2), r);
            cout << s1+s2+s3 << "\n";
        }else{
            for(int i = 1; i <= k; i++){
                cin >> c[i];
            }
            int cpval = v[c[1]];
            for(int i = 2; i <= k; i++){
                int prev_val = v[c[i-1]];
                v[c[i-1]] = v[c[i]];
            }
            v[c[k]] = cpval;
            for(int i = 1; i <= k; i++){
                int dif = v[c[i]]-cpy[c[i]];
                update(a, c[i], dif);
                dif = c[i]*v[c[i]] - c[i]*cpy[c[i]];
                update(asc, c[i], dif);
                dif = (n-c[i]+1)*v[c[i]] - (n-c[i]+1)*cpy[c[i]];
                update(desc, c[i], dif);
                cpy[c[i]] = v[c[i]];
            }
        }
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:61:21: warning: unused variable 'prev_val' [-Wunused-variable]
   61 |                 int prev_val = v[c[i-1]];
      |                     ^~~~~~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 5 ms 448 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 10 ms 596 KB Output is correct
6 Correct 12 ms 684 KB Output is correct
7 Correct 15 ms 764 KB Output is correct
8 Correct 19 ms 784 KB Output is correct
9 Correct 26 ms 1028 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1784 KB Output is correct
2 Correct 73 ms 2520 KB Output is correct
3 Correct 101 ms 3404 KB Output is correct
4 Correct 177 ms 5928 KB Output is correct
5 Correct 254 ms 8148 KB Output is correct
6 Correct 225 ms 7944 KB Output is correct
7 Correct 235 ms 7920 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 4656 KB Output is correct
2 Correct 212 ms 6908 KB Output is correct
3 Correct 333 ms 9508 KB Output is correct
4 Correct 273 ms 8396 KB Output is correct