Submission #526852

#	Time	Username	Problem	Language	Result	Execution time	Memory
526852		arnav2004	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	252 ms	8204 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MX = 1e5 + 5;
int N,M,K,A[MX];
pair<int,int> seg[4 * MX];
pair<int,int> calculate(const pair<int,int> &x, const pair<int,int> &y){
  return {x.first + y.first, max(x.second, y.second)};
}
void build(int idx, int low, int high){
  if(low == high){
    seg[idx] = {A[low], A[low]};
    return;
  }
  int mid = (low + high) >> 1;
  build(idx * 2 + 1, low, mid);
  build(idx * 2 + 2, mid + 1, high);
  seg[idx] = calculate(seg[idx * 2 + 1], seg[idx * 2 + 2]);
}
int query(int idx, int low, int high, int L, int R){
  if(L <= low && high <= R)
    return seg[idx].first;
  if(low > R || high < L)
    return 0;
  int mid = (low + high) >> 1;
  return query(idx * 2 + 1, low, mid, L, R) + query(idx * 2 + 2, mid + 1, high, L, R);
}
int get_max(int idx, int low, int high, int L, int R){
  if(L <= low && high <= R)
    return seg[idx].second;
  if(low > R || high < L)
    return 0;
  int mid = (low + high) >> 1;
  return max(get_max(idx * 2 + 1, low, mid, L, R), get_max(idx * 2 + 2, mid + 1, high, L, R));
}
void update(int idx, int low, int high, int L, int R, int v){
  if(L <= low && high <= R){
    seg[idx] = {v, v};
    return;
  }
  if(low > R || high < L)
    return;
  int mid = (low + high) >> 1;
  update(idx * 2 + 1, low, mid, L, R, v);
  update(idx * 2 + 2, mid + 1, high, L, R, v);
  seg[idx] = calculate(seg[idx * 2 + 1], seg[idx * 2 + 2]);
}
void update2(int idx, int low, int high, int L, int R){
  if(low > R || high < L) return;
  if(seg[idx].second == 0) return;
  if(low == high){
    A[low] /= K;
    seg[idx] = {A[low], A[low]};
    return;
  }
  int mid = (low + high) >> 1;
  update2(idx * 2 + 1, low, mid, L, R);
  update2(idx * 2 + 2, mid + 1, high, L, R);
  seg[idx] = calculate(seg[idx * 2 + 1], seg[idx * 2 + 2]);
}
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M >> K;
  for(int i = 0; i < N; i++)
    cin >> A[i];
  build(0, 0, N - 1);
  while(M--){
    int T; cin >> T;
    if(T == 3){
      int L,R; cin >> L >> R;
      L--; R--;
      cout << query(0, 0, N - 1, L, R) << '\n';
    }
    else if(T == 2){
      int L,R; cin >> L >> R;
      L--; R--;
      if(K == 1) continue;
      update2(0, 0, N - 1, L, R);
    }
    else{
      int k,x; cin >> k >> x;
      k--;
      A[k] = x;
      update(0, 0, N - 1, k, k, x);
    }
  }
  return 0;
}

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