제출 #543659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543659		tudor	Addk (eJOI21_addk)	C++17	0 / 100	1 ms	340 KiB

Main

#include <fstream>

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];

ifstream cin ( "addk.in" );
ofstream cout ( "addk.out" );

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: 0 / 36
• Subtask 2: 0 / 56
• Subtask 3: 0 / 8