oj.uz

Submission #1043890

# Submission time Handle Problem Language Result Execution time Memory
1043890 2024-08-05T03:01:32 Z devariaota Addk (eJOI21_addk) C++17
100 / 100
 294 ms 17236 KB 
#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e5;

bool hack = 0;
int n, k, q, a[maxn+5], b[maxn+5], st_pref[4*maxn+5], st_preg[4*maxn+5], st_gerp[4*maxn+5], pos[maxn+5];

void up_pref(int id, int ss, int se, int po, int va) {
  if (ss == se) {
    st_pref[id] = va;
    return;
  }
  int mi = (ss + se)/2;
  if (po <= mi) up_pref(2*id, ss, mi, po, va);
  else up_pref(2*id+1, mi+1, se, po, va);
  st_pref[id] = st_pref[2*id] + st_pref[2*id+1];
}

void up_preg(int id, int ss, int se, int po, int va) {
  if (ss == se) {
    st_preg[id] = ss*va;
    return;
  }
  int mi = (ss + se)/2;
  if (po <= mi) up_preg(2*id, ss, mi, po, va);
  else up_preg(2*id+1, mi+1, se, po, va);
  st_preg[id] = st_preg[2*id] + st_preg[2*id+1];  
}

void up_gerp(int id, int ss, int se, int po, int va) {
  if (ss == se) {
    st_gerp[id] = (n-ss+1)*va;
    return;
  }
  int mi = (ss + se)/2;
  if (po <= mi) up_gerp(2*id, ss, mi, po, va);
  else up_gerp(2*id+1, mi+1, se, po, va);
  st_gerp[id] = st_gerp[2*id] + st_gerp[2*id+1];    
}

int pref(int id, int ss, int se, int qs, int qe) {
  if (qs <= ss && se <= qe) return st_pref[id];
  if (se < qs || qe < ss) return 0;
  int mi = (ss + se)/2;
  return pref(2*id, ss, mi, qs, qe) + pref(2*id+1, mi+1, se, qs, qe);
}

int preg(int id, int ss, int se, int qs, int qe) {
  if (qs <= ss && se <= qe) return st_preg[id];
  if (se < qs || qe < ss) return 0;
  int mi = (ss + se)/2;
  return preg(2*id, ss, mi, qs, qe) + preg(2*id+1, mi+1, se, qs, qe);
}

int gerp(int id, int ss, int se, int qs, int qe) {
  if (qs <= ss && se <= qe) return st_gerp[id];
  if (se < qs || qe < ss) return 0;
  int mi = (ss + se)/2;
  return gerp(2*id, ss, mi, qs, qe) + gerp(2*id+1, mi+1, se, qs, qe);
}

signed main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> k;
  for (int i=1; i<=n; i++) {
    cin >> a[i];
    up_pref(1, 1, n, i, a[i]);
    up_preg(1, 1, n, i, a[i]);
    up_gerp(1, 1, n, i, a[i]);
  }
  cin >> q;
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      for (int i=1; i<=k; i++) {
        cin >> pos[i];
      }
      if (k == 1) continue;
      for (int i=1; i<=k; i++) {
        b[pos[i]] = a[ pos[(i+1)%k + k*(i==k-1)] ];
        up_pref(1, 1, n, pos[i], a[ pos[(i+1)%k + k*(i==k-1)] ]);
        up_preg(1, 1, n, pos[i], a[ pos[(i+1)%k + k*(i==k-1)] ]);
        up_gerp(1, 1, n, pos[i], a[ pos[(i+1)%k + k*(i==k-1)] ]);
      }
      for (int i=1; i<=k; i++) {
        if (hack) cout << "b" << pos[i] << ": " << b[pos[i]] << endl;
        a[pos[i]] = b[pos[i]];
      }
      if (hack) {
        cout << "array after update: " << endl;
        for (int i=1; i<=n; i++) cout << a[i] << " ";
        cout << endl;
      }
    }
    else {
      int l, r, m;
      cin >> l >> r >> m;
      int len = r - l + 1;
      int h = min(len-m+1, m);
      int x = l + h - 1, y = r - h + 1;
      int ans = h*pref(1, 1, n, x, y)  +  preg(1, 1, n, l, x-1) - (l-1)*pref(1, 1, n, l, x-1)  +  gerp(1, 1, n, y+1, r) - (n-r)*pref(1, 1, n, y+1, r);
      cout << ans << endl;
    }
  }
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 4 ms 6492 KB Output is correct
4 Correct 6 ms 6488 KB Output is correct
5 Correct 8 ms 6672 KB Output is correct
6 Correct 15 ms 6720 KB Output is correct
7 Correct 12 ms 6748 KB Output is correct
8 Correct 14 ms 6668 KB Output is correct
9 Correct 20 ms 6744 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9044 KB Output is correct
2 Correct 63 ms 9296 KB Output is correct
3 Correct 86 ms 9300 KB Output is correct
4 Correct 154 ms 12140 KB Output is correct
5 Correct 268 ms 12880 KB Output is correct
6 Correct 202 ms 12820 KB Output is correct
7 Correct 198 ms 12736 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 11604 KB Output is correct
2 Correct 197 ms 15220 KB Output is correct
3 Correct 294 ms 17236 KB Output is correct
4 Correct 257 ms 16212 KB Output is correct