Submission #1262001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262001		meisgood	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	152 ms	4828 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std ;
#define int long long
int A[100003] ;
int n,q,k ;
struct SEGT{
  int seg[400003] ;
  void build(int id,int l,int r){
    if (l==r) seg[id]=A[l] ;
    else {
      int md=(l+r)/2 ;
      build(id*2,l,md) ;
      build(id*2+1,md+1,r) ;
      seg[id]=seg[id*2]+seg[id*2+1] ;
    }
  }
  void upd(int id,int l,int r,int ql,int qr){
    if (seg[id]==0) return ;
    if (l>qr||r<ql) return ;
    if (l==r){
      seg[id]/=k ;
    }
    else {
      int md=(l+r)/2 ;
      upd(id*2,l,md,ql,qr) ;
      upd(id*2+1,md+1,r,ql,qr) ;
      seg[id]=seg[id*2]+seg[id*2+1] ;
    }
  }
  void upd2(int id,int l,int r,int x,int v){
    if (l==r&&l==x) seg[id]=v ;
    else if (l>x||r<x) return ;
    else {
      int md=(l+r)/2 ;
      upd2(id*2,l,md,x,v) ;
      upd2(id*2+1,md+1,r,x,v) ;
      seg[id]=seg[id*2]+seg[id*2+1] ;
    }
  }
  int qq(int id,int l,int r,int ql,int qr){
    if (ql<=l&&r<=qr) return seg[id] ;
    else if (l>qr||r<ql) return 0 ;
    else {
      int md=(l+r)/2 ;
      return qq(id*2,l,md,ql,qr)+qq(id*2+1,md+1,r,ql,qr) ;
    }
  }
} ;
signed main(){
  int i,j ;
  cin >> n >> q >> k ;
  for (i = 1 ; i <= n ; i ++){
    cin >> A[i] ;
  }
  SEGT sgt ;
  sgt.build(1,1,n) ;
  while (q--){
    int T ;
    int a,b ;
    cin >> T ;
    cin >> a >> b ;
    if (T==1){
      sgt.upd2(1,1,n,a,b) ;
    }
    else if (T==2){
      if (k!=1) sgt.upd(1,1,n,a,b) ;
    }
    else {
      cout << sgt.qq(1,1,n,a,b) << endl ;
    }
  }
	return 0 ;
}

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