Submission #1071846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071846		horiaboeriu	Addk (eJOI21_addk)	C++17	92 / 100	48 ms	6996 KiB

Main

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXN 200000
#define MAXK 10
long long aibv[MAXN + 1], aibsp[MAXN + 1];
int v[MAXN + 1], vpoz[MAXK];
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;
}
void addBit(int poz, int n, long long val, long long aib[]) {
    while (poz <= n) {
        aib[poz] += val;
        poz += (poz & (-poz));
    }
}
long long bitSum(int poz, long long aib[]) {
    long long s;
    s = 0;
    while (poz > 0) {
        s += aib[poz];
        poz &= (poz - 1);
    }
    return s;
}
long long calcspsp(int st, int dr) {//calculeaza suma partiala dintre sumele partiale de la st la dr
    return bitSum(dr, aibsp) - bitSum(st - 1, aibsp);
}
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 voi face sume partiale si sume partiale la sume partiale cu aib*/
    int n, q, i, k, cer, j, x, st, dr, m;
    long long s;
    n = readInt();
    k = readInt();
    s = 0;
    for (i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        s += v[i];//suma partiala pana la i
        addBit(i, n, v[i], aibv);
        addBit(i, n, s, aibsp);
    }
    q = readInt();
    for (i = 0; i < q; i++) {
        cer = readInt();
        if (cer == 1) {
            for (j = 0; j < k; j++) {
                vpoz[j] = readInt();
            }
            if (k > 1) {
                x = v[vpoz[0]];
                for (j = 1; j < k; j++) {
                    s = bitSum(vpoz[j - 1], aibv);
                    addBit(vpoz[j - 1], n, v[vpoz[j]] - v[vpoz[j - 1]], aibv);
                    addBit(vpoz[j - 1], n, s + v[vpoz[j]] - v[vpoz[j - 1]], aibsp);//suma partiala de pe poz vpoz[j - 1] creste cu cat am adaugat la v[vpoz[j]] - v[vpoz[j - 1]]
                    v[vpoz[j - 1]] = v[vpoz[j]];
                }
                //acum il schimb pe ultimul cu primul
                s = bitSum(vpoz[k - 1], aibv);
                addBit(vpoz[k - 1], n, x - v[vpoz[k - 1]], aibv);
                addBit(vpoz[k - 1], n, s + x - v[vpoz[k - 1]], aibsp);
                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
                printf("%lld\n", calcspsp(dr - m + 1, dr) - calcspsp(st - 1, st + m - 2));
            } 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;
                printf("%lld\n", calcspsp(dr - m + 1, dr) - calcspsp(st - 1, st + m - 2));
            }
        }
    }
    return 0;
}

Compilation message (stderr)

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

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