제출 #436906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436906		peijar	Sterilizing Spray (JOI15_sterilizing)	C++17	80 / 100	5099 ms	12084 KiB

sterilizing

#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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 75 / 75