Submission #1073021

#TimeUsernameProblemLanguageResultExecution timeMemory
1073021raduvAddk (eJOI21_addk)C++14
92 / 100
93 ms11604 KiB
#include <bits/stdc++.h> #define int long long const int MAXN = 100'005; const int MAXK = 15; int sp[MAXN + 1]; int v[MAXN + 1]; int aint[(MAXN + 1) * 4]; int no_nums[(MAXN + 1) * 4]; int poz[MAXK]; int lazy[(MAXN + 1) * 4]; void propagate(int node){ lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; aint[2 * node] += lazy[node] * no_nums[2 * node]; aint[2 * node + 1] += lazy[node] * no_nums[2 * node + 1]; lazy[node] = 0; } void build(int node, int st, int dr){ if(st == dr){ aint[node] = sp[st]; no_nums[node] = 1; } else{ int mij = (st + dr) / 2; build(2 * node, st, mij); build(2 * node + 1, mij + 1, dr); aint[node] = (aint[2 * node] + aint[2 * node + 1]); no_nums[node] = (no_nums[2 * node] + no_nums[2 * node + 1]); } } void update(int node, int st, int dr, int l, int r, int val){ if(l <= st && dr <= r){ aint[node] += no_nums[node] * val; lazy[node] += val; } else{ if(lazy[node] > 0) propagate(node); int mij = (st + dr) / 2; if(l <= mij) update(2 * node, st, mij, l, r, val); if(r > mij) update(2 * node + 1, mij + 1, dr, l, r, val); aint[node] = (aint[2 * node] + aint[2 * node + 1]); } } int query(int node, int st, int dr, int l, int r){ if(l <= st && dr <= r){ return aint[node]; } else{ if(lazy[node] > 0) propagate(node); int mij = (st + dr) / 2, sum = 0; if(l <= mij) sum += query(2 * node, st, mij, l, r); if(r > mij) sum += query(2 * node + 1, mij + 1, dr, l, r); return sum; } } signed main() { int n, k, q, i, tip, j, aux, l, r, m, s1, s2; scanf("%lld%lld", &n, &k); for( i = 1; i <= n; i++ ){ scanf("%lld", &v[i]); sp[i] = sp[i - 1] + v[i]; } build(1, 1, n); scanf("%lld", &q); for( i = 0; i < q; i++ ){ scanf("%lld", &tip); if(tip == 1){ for( j = 0; j < k; j++ ) scanf("%lld", &poz[j]); aux = v[poz[0]]; for( j = 1; j < k; j++ ){ update(1, 1, n, poz[j - 1], n, v[poz[j]] - v[poz[j - 1]]); v[poz[j - 1]] = v[poz[j]]; } update(1, 1, n, poz[k - 1], n, aux - v[poz[k - 1]]); v[poz[k - 1]] = aux; } else{ scanf("%lld%lld%lld", &l, &r, &m); s1 = query(1, 1, n, l + m - 1, r); s2 = query(1, 1, n, std::max(1LL, l - 1), std::max(1LL, r - m)); printf("%lld\n", s1 - s2); } } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%lld%lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:69:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |       scanf("%lld", &v[i]);
      |       ~~~~~^~~~~~~~~~~~~~~
Main.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%lld", &q);
      |     ~~~~~^~~~~~~~~~~~
Main.cpp:75:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |       scanf("%lld", &tip);
      |       ~~~~~^~~~~~~~~~~~~~
Main.cpp:78:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |           scanf("%lld", &poz[j]);
      |           ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%lld%lld%lld", &l, &r, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...