Submission #124796

#	Time	Username	Problem	Language	Result	Execution time	Memory
124796		iqvocuc	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	543 ms	5732 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
int n, q, k;
long long a[100100];
long long st[200200];
void build(int id, int l, int r) {
   if (l == r) {
      st[id] =  a[l];
      return;
   }
   int mid=(l+r)/2;
   build(id*2,l,mid);
   build(id*2+1, mid + 1, r);
   st[id] = st[id*2] + st[id *2 +1 ];
}
void truyvan2(int id, int l, int r, int L, int R) {
   if (st[id] == 0 || k == 1) return;
   if (l == r) {
      st[id] /= k;
      return;
   }
   int mid=(l+r)/2;
 if(L<=mid)  truyvan2(id*2, l, mid, L, R);
  if(R>mid)  truyvan2(id*2+1, mid + 1, r, L, R);
   st[id] = st[id*2] + st[id*2+1];
}
void truyvan1(int id, int l, int r, int L, int R) {
   if (l == r) {
      st[id] = R;
      return;
   }
   int mid=(l+r)/2;
   if (L <= mid) truyvan1(id*2, l, mid, L, R);
   else truyvan1(id*2+1, mid + 1, r, L, R);
   st[id] = st[id*2] + st[id*2+1];
}
long long truyvan3(int id, int l, int r, int u, int v) {
   if (u <= l && r <= v) return st[id];
   long long tong = 0;
   int mid=(l+r)/2;
   if (u <= mid) tong += truyvan3(id*2, l, mid, u, v);
   if (mid < v) tong += truyvan3(id*2+1, mid + 1, r, u, v);
   return tong;
}
int main (){
   cin >> n >> q >> k;
   for (int i = 1; i <= n; ++i) {
      cin >> a[i];
   }
   build(1, 1, n);
   while (q--) {
      int query;
      cin >> query;
      if (query == 1) {
         int x, y;
         cin >> x>> y;
         truyvan1(1, 1, n, x, y);
      } else if (query == 2) {
         int xx, yy;
         cin >> xx >> yy;
         truyvan2(1, 1, n, xx, yy);
      } else {
         int xx, yy;
         cin >> xx >> yy;
         cout << truyvan3(1, 1, n, xx,yy) << endl;
      }
   }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75