Submission #1073359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073359		horiaboeriu	Addk (eJOI21_addk)	C++17	100 / 100	149 ms	10576 KiB

Main

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXN 100000
#define MAXK 10
long long a[4 * MAXN], v1[4 * MAXN], sp[MAXN + 1];
int vnr[4 * MAXN];//cate numere sunt in acel nod
char flag[4 * MAXN];
int v[MAXN + 1], vpoz[MAXK];
long long sum;
void lazy(int nod) {
    v1[2 * nod] += v1[nod];
    v1[2 * nod + 1] += v1[nod];
    a[2 * nod] += v1[nod] * vnr[2 * nod];
    a[2 * nod + 1] += v1[nod] * vnr[2 * nod + 1];
    flag[2 * nod] = flag[2 * nod + 1] = 1;
    flag[nod] = v1[nod] = 0;
}
void build(int nod, int st, int dr) {
    int mid;
    if (st == dr) {
        a[nod] = sp[st];
        vnr[nod] = 1;
    } else {
        mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
        a[nod] = a[2 * nod] + a[2 * nod + 1];
        vnr[nod] = vnr[2 * nod] + vnr[2 * nod + 1];
    }
}
void update(int nod, int st, int dr, int x, int y, int val) {
    int mid;
    if (x <= st && y >= dr) {
        a[nod] += (long long)val * vnr[nod];
        v1[nod] += val;
        flag[nod] = 1;
    } else {
        mid = (st + dr) / 2;
        if (flag[nod] > 0) {
            lazy(nod);
        }
        if (x <= mid) {
            update(2 * nod, st, mid, x, y, val);
        }
        if (y > mid) {
            update(2 * nod + 1, mid + 1, dr, x, y, val);
        }
        a[nod] = a[2 * nod] + a[2 * nod + 1];
    }
}
void query(int nod, int st, int dr, int x, int y) {
    int mid;
    if (x <= st && y >= dr) {
        sum += a[nod];
    } else {
        mid = (st + dr) / 2;
        if (flag[nod] > 0) {
            lazy(nod);
        }
        if (x <= mid) {
            query(2 * nod, st, mid, x, y);
        }
        if (y > mid) {
            query(2 * nod + 1, mid + 1, dr, x, y);
        }
        //a[nod] = a[2 * nod] + a[2 * nod + 1];
    }
}
int readInt() {
    int x;
    char ch;
    ch = fgetc(stdin);
    while (isspace(ch)) {
        ch = fgetc(stdin);
    }
    x = 0;
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = fgetc(stdin);
    }
    return x;
}
int main()
{
    /*am un exemplu
    l = 1 r = 7 m = 3
    (1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 5, 6), (5, 6, 7)
    1, 7 - apar o data
    2, 6 - apar de doua ori
    3, 4, 5 - apar de m ori, m = 3
    sp[7] - sp[0] + sp[6] - sp[1] + sp[5] - sp[2]
    = sp[5] + sp[6] + sp[7] - sp[0] - sp[1] - sp[2]
    deci imi trebuie sume partiale la sume partiale
    pentru ca sunt actualizari, cand un element de pe pozitia poz se schimba, toate sumele partiale de la poz pana la n se schimba
    voi face un aint cu lazy ca sa stiu cat este fiecare suma partiala, se poate face si cu aib*/
    int n, q, i, k, cer, j, x, st, dr, m;
    long long s1, s2;
    n = readInt();
    k = readInt();
    for (i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        sp[i] = sp[i - 1] + v[i];
    }
    build(1, 1, n);
    q = readInt();
    for (i = 0; i < q; i++) {
        cer = readInt();
        if (cer == 1) {
            for (j = 0; j < k; j++) {
                vpoz[j] = readInt();
            }
            x = v[vpoz[0]];
            for (j = 1; j < k; j++) {
                update(1, 1, n, vpoz[j - 1], n, v[vpoz[j]] - v[vpoz[j - 1]]);
                v[vpoz[j - 1]] = v[vpoz[j]];
            }
            //acum il schimb pe ultimul cu primul
            update(1, 1, n, vpoz[k - 1], n, x - v[vpoz[k - 1]]);
            v[vpoz[k - 1]] = x;
        } else {
            st = readInt();
            dr = readInt();
            m = readInt();
            if (m <= (dr - st + 2) / 2) {
                //atunci st si dr apar o data, st + 1 si dr - 1 de doua ori si tot asa pana cadn cele din centru o sa apara de m ori
                sum = 0;
                query(1, 1, n, dr - m + 1, dr);
                s1 = sum;
                sum = 0;
                if (st == 1) {
                    query(1, 1, n, st, st + m - 2);
                } else {
                    query(1, 1, n, st - 1, st + m - 2);
                }
                s2 = sum;
                printf("%lld\n", s1 - s2);
            } else {
                //cele din margini o sa apara de la fel de multe ori, dar de cele mai multe ori vor fi tot cele din centru, dar acesteea vor aparea de (dr - st + 2) - m ori
                m = (dr - st + 2) - m;
                sum = 0;
                query(1, 1, n, dr - m + 1, dr);
                s1 = sum;
                sum = 0;
                if (st == 1) {
                    query(1, 1, n, st, st + m - 2);
                } else {
                    query(1, 1, n, st - 1, st + m - 2);
                }
                s2 = sum;
                printf("%lld\n", s1 - s2);
            }
        }
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         scanf("%d", &v[i]);
      |         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8