oj.uz

Submission #543660

# Submission time Handle Problem Language Result Execution time Memory
543660 2022-03-31T07:57:21 Z tudor Addk (eJOI21_addk) C++17
100 / 100
 379 ms 7560 KB 
#include <iostream>

using namespace std;
const int nmax = 1e5;
const int kmax = 10;

int n;
long long aib[2][nmax + 1];
/// query ( aib[0], n ) -> suma v[i], 1 <= i <= n
/// query ( aib[1], n ) -> suma v[i] * i, 1 <= i <= n

void update ( int p, int poz, long long add ) {
    for ( ; poz <= n; poz += poz & -poz )
        aib[p][poz] += add;
}

long long query ( int p, int poz ) {
    long long s = 0;
    for ( ; poz > 0; poz -= poz & -poz )
        s += aib[p][poz];
    return s;
}

long long sum ( int p, int a, int b ) {
    return query ( p, b ) - query ( p, a - 1 );
}

int v[nmax + 1];
int ind[kmax + 1];

int main() {
    int k, q, tip, l, r, m;

    cin >> n >> k;
    for ( int i = 1; i <= n; i++ ) {
        cin >> v[i];
        update ( 0, i, v[i] );
        update ( 1, i, ( long long ) i * v[i] );
    }

    cin >> q;
    while ( q-- ) {

        cin >> tip;

        if ( tip == 1 )  {
            for ( int i = 1; i <= k; i++ )
                cin >> ind[i];

            int a = v[ind[1]];
            for ( int i = 1; i <= k - 1; i++ ) {
                update ( 0, ind[i], v[ind[i + 1]] - v[ind[i]] );
                update ( 1, ind[i], ( long long ) ind[i] * ( v[ind[i + 1]] - v[ind[i]] ) );
                v[ind[i]] = v[ind[i + 1]];
            }
            update ( 0, ind[k], a - v[ind[k]] );
            update ( 1, ind[k], ( long long ) ind[k] * ( a - v[ind[k]] ) );
            v[ind[k]] = a;

        } else {

            cin >> l >> r >> m;

            long long a, b, c;
            if ( r - l + 1 <= 2 * m ) {
                a = sum ( 1, l, r - m ) - ( long long ) ( l - 1 ) * sum ( 0, l, r - m );
                b = ( long long ) ( r - m - l + 2 ) * sum ( 0, r - m + 1, l + m - 1 );
                c = ( long long ) ( r + 1 ) * sum ( 0, l + m, r ) - sum ( 1, l + m, r );
                cout << a + b + c << '\n';
            } else {
                a = sum ( 1, l, l + m - 2 ) - ( long long ) ( l - 1 ) * sum ( 0, l, l + m - 2 );
                b = ( long long ) m * sum ( 0, l + m - 1, r - m + 1 );
                c = ( long long ) ( r + 1 ) * sum ( 0, r - m + 2, r ) - sum ( 1, r - m + 2, r );
                cout << a + b + c << '\n';
            }

        }

    }

    return 0;
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 324 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 8 ms 476 KB Output is correct
5 Correct 13 ms 456 KB Output is correct
6 Correct 14 ms 468 KB Output is correct
7 Correct 20 ms 616 KB Output is correct
8 Correct 18 ms 676 KB Output is correct
9 Correct 26 ms 844 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 1384 KB Output is correct
2 Correct 84 ms 1912 KB Output is correct
3 Correct 106 ms 2636 KB Output is correct
4 Correct 177 ms 4396 KB Output is correct
5 Correct 342 ms 6164 KB Output is correct
6 Correct 279 ms 6000 KB Output is correct
7 Correct 290 ms 5880 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 3644 KB Output is correct
2 Correct 257 ms 5292 KB Output is correct
3 Correct 379 ms 7560 KB Output is correct
4 Correct 331 ms 6460 KB Output is correct