oj.uz

Submission #436906

# Submission time Handle Problem Language Result Execution time Memory
436906 2021-06-25T08:13:10 Z peijar Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 12084 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])
    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 460 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 7 ms 588 KB Output is correct
6 Correct 5 ms 664 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 6 ms 716 KB Output is correct
10 Correct 5 ms 696 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 5 ms 700 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5099 ms 6700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1356 KB Output is correct
2 Correct 18 ms 5072 KB Output is correct
3 Correct 24 ms 5196 KB Output is correct
4 Correct 65 ms 3732 KB Output is correct
5 Correct 98 ms 10700 KB Output is correct
6 Correct 113 ms 10684 KB Output is correct
7 Execution timed out 5015 ms 10104 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 6536 KB Output is correct
2 Correct 125 ms 6724 KB Output is correct
3 Correct 163 ms 6160 KB Output is correct
4 Correct 150 ms 4588 KB Output is correct
5 Correct 249 ms 12084 KB Output is correct
6 Correct 259 ms 12032 KB Output is correct
7 Correct 188 ms 11924 KB Output is correct
8 Correct 274 ms 11960 KB Output is correct
9 Correct 241 ms 11940 KB Output is correct
10 Correct 274 ms 11844 KB Output is correct
11 Correct 202 ms 11820 KB Output is correct
12 Correct 366 ms 11892 KB Output is correct