Submission #1073360

#TimeUsernameProblemLanguageResultExecution timeMemory
1073360horiaboeriuAddk (eJOI21_addk)C++17
100 / 100
150 ms9556 KiB
#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++) { v[i] = readInt(); 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...