oj.uz

Submission #436907

# Submission time Handle Problem Language Result Execution time Memory
436907 2021-06-25T08:14:30 Z peijar Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 362 ms 12228 KB 
#include <bits/stdc++.h>
#include <type_traits>
#define int long long
using namespace std;

const int MAXN = (1 << 18) + 1;

int sum[MAXN], allZero[MAXN];
int iDeb[MAXN], iFin[MAXN];
int vals[MAXN];

void buildTree(int iNoeud, int deb, int fin) {
  iDeb[iNoeud] = deb;
  iFin[iNoeud] = fin;
  if (deb == fin) {
    sum[iNoeud] = vals[deb];
    allZero[iNoeud] = !vals[deb];
    return;
  }
  int mid = (deb + fin) / 2;
  buildTree(2 * iNoeud, deb, mid);
  buildTree(2 * iNoeud + 1, mid + 1, fin);
  sum[iNoeud] = sum[2 * iNoeud] + sum[2 * iNoeud + 1];
  allZero[iNoeud] = !sum[iNoeud];
}

void update(int iNoeud, int deb, int fin, int d) {
  if (iDeb[iNoeud] > fin or iFin[iNoeud] < deb or allZero[iNoeud] or d == 1)
    return;

  if (iDeb[iNoeud] == iFin[iNoeud]) {
    sum[iNoeud] /= d;
    allZero[iNoeud] = !sum[iNoeud];
    return;
  }
  update(2 * iNoeud, deb, fin, d);
  update(2 * iNoeud + 1, deb, fin, d);
  sum[iNoeud] = sum[2 * iNoeud] + sum[2 * iNoeud + 1];
  allZero[iNoeud] = !sum[iNoeud];
}

void setVal(int iNoeud, int pos, int v) {
  if (iDeb[iNoeud] > pos or iFin[iNoeud] < pos)
    return;
  if (iDeb[iNoeud] == iFin[iNoeud]) {
    sum[iNoeud] = v;
    allZero[iNoeud] = !v;
    return;
  }
  setVal(2 * iNoeud, pos, v);
  setVal(2 * iNoeud + 1, pos, v);
  sum[iNoeud] = sum[2 * iNoeud] + sum[2 * iNoeud + 1];
  allZero[iNoeud] = !sum[iNoeud];
}

int query(int iNoeud, int deb, int fin) {
  if (iDeb[iNoeud] > fin or iFin[iNoeud] < deb)
    return 0;
  if (iDeb[iNoeud] >= deb and iFin[iNoeud] <= fin)
    return sum[iNoeud];
  return query(2 * iNoeud, deb, fin) + query(2 * iNoeud + 1, deb, fin);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbElem, nbRequetes, d;
  cin >> nbElem >> nbRequetes >> d;

  for (int i = 0; i < nbElem; ++i)
    cin >> vals[i];
  buildTree(1, 0, nbElem - 1);

  for (int i = 0; i < nbRequetes; ++i) {
    int s, t, u;
    cin >> s >> t >> u;
    if (s == 1)
      setVal(1, t - 1, u);
    else if (s == 2)
      update(1, t - 1, u - 1, d);
    else
      cout << query(1, t - 1, u - 1) << '\n';
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 5 ms 588 KB Output is correct
8 Correct 5 ms 588 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 4 ms 588 KB Output is correct
12 Correct 5 ms 636 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 5420 KB Output is correct
2 Correct 74 ms 6596 KB Output is correct
3 Correct 67 ms 11012 KB Output is correct
4 Correct 76 ms 11768 KB Output is correct
5 Correct 109 ms 12228 KB Output is correct
6 Correct 107 ms 12224 KB Output is correct
7 Correct 109 ms 12140 KB Output is correct
8 Correct 102 ms 12172 KB Output is correct
9 Correct 91 ms 12100 KB Output is correct
10 Correct 91 ms 12012 KB Output is correct
11 Correct 95 ms 12200 KB Output is correct
12 Correct 84 ms 11972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 916 KB Output is correct
2 Correct 19 ms 4796 KB Output is correct
3 Correct 31 ms 4804 KB Output is correct
4 Correct 67 ms 2604 KB Output is correct
5 Correct 98 ms 9308 KB Output is correct
6 Correct 106 ms 9292 KB Output is correct
7 Correct 93 ms 10128 KB Output is correct
8 Correct 117 ms 10692 KB Output is correct
9 Correct 90 ms 10560 KB Output is correct
10 Correct 87 ms 10560 KB Output is correct
11 Correct 92 ms 10596 KB Output is correct
12 Correct 93 ms 10704 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 4968 KB Output is correct
2 Correct 127 ms 5032 KB Output is correct
3 Correct 144 ms 4920 KB Output is correct
4 Correct 161 ms 2896 KB Output is correct
5 Correct 212 ms 9544 KB Output is correct
6 Correct 239 ms 9528 KB Output is correct
7 Correct 241 ms 9664 KB Output is correct
8 Correct 319 ms 9472 KB Output is correct
9 Correct 234 ms 9580 KB Output is correct
10 Correct 304 ms 9540 KB Output is correct
11 Correct 201 ms 9696 KB Output is correct
12 Correct 362 ms 9540 KB Output is correct