oj.uz

Submission #539743

# Submission time Handle Problem Language Result Execution time Memory
539743 2022-03-19T06:55:08 Z cig32 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 253 ms 6912 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { // read int128
  int x; cin >> x; return (ll)x;
}
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD);
}
int st[4*MAXN];

void u1(int l, int r, int tar, int idx, int val) {
  if(l == r) {
    st[idx] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if(tar <= mid) u1(l, mid, tar, 2*idx+1, val);
  else u1(mid+1, r, tar, 2*idx+2, val);
  st[idx] = st[2*idx+1] + st[2*idx+2];
}
void u2(int l, int r, int constl, int constr, int idx, int val) {
  if(constl == constr) {
    st[idx] /= val;
    return;
  }
  if(st[idx] == 0) return;
  int mid = (constl+constr) >> 1;
  if(mid<l || r<constl) u2(l, r, mid+1, constr, 2*idx+2, val);
  else if(constr<l || r<mid+1) u2(l, r, constl, mid, 2*idx+1, val);
  else {
    u2(l, r, constl, mid, 2*idx+1, val);
    u2(l, r, mid+1, constr, 2*idx+2, val);
  }
  st[idx] = st[2*idx+1] + st[2*idx+2];
}
int qu(int l, int r, int constl, int constr, int idx) {
  if(l<=constl && constr<=r) return st[idx];
  int mid = (constl+constr) >> 1;
  if(mid<l || r<constl) return qu(l, r, mid+1, constr, 2*idx+2);
  else if(constr<l || r<mid+1) return qu(l, r,constl, mid,2*idx+1);
  else {
    return qu(l, r, constl, mid, 2*idx+1) + qu(l, r, mid+1, constr, 2*idx+2);
  }
}

void point_update(int i, int v) {
  u1(0, MAXN - 1, i, 0, v);
}

void range_divide(int l, int r, int k) {
  if(k == 1) return;
  u2(l, r, 0, MAXN - 1, 0, k);
}

int query_sum(int l, int r) {
  return qu(l, r, 0, MAXN - 1, 0);
}

void solve(int tc) {
  int n, q, k;
  cin >> n >> q >> k;
  for(int i=1; i<=n; i++) {
    int st;
    cin >> st;
    point_update(i, st);
  }
  while(q--) {
    int s, t, u;
    cin >> s >> t >> u;
    if(s == 1) {
      point_update(t, u);
    }
    else if(s == 2) {
      range_divide(t, u, k);
    }
    else {
      cout << query_sum(t, u) << "\n";
    }
  }
}
int32_t main(){
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1876 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 5 ms 1916 KB Output is correct
4 Correct 6 ms 2004 KB Output is correct
5 Correct 8 ms 2132 KB Output is correct
6 Correct 5 ms 2040 KB Output is correct
7 Correct 5 ms 2032 KB Output is correct
8 Correct 6 ms 2072 KB Output is correct
9 Correct 6 ms 2004 KB Output is correct
10 Correct 6 ms 2004 KB Output is correct
11 Correct 6 ms 2004 KB Output is correct
12 Correct 9 ms 2184 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5228 KB Output is correct
2 Correct 45 ms 4640 KB Output is correct
3 Correct 42 ms 5432 KB Output is correct
4 Correct 52 ms 6384 KB Output is correct
5 Correct 83 ms 6804 KB Output is correct
6 Correct 76 ms 6912 KB Output is correct
7 Correct 93 ms 6888 KB Output is correct
8 Correct 85 ms 6896 KB Output is correct
9 Correct 65 ms 6756 KB Output is correct
10 Correct 91 ms 6660 KB Output is correct
11 Correct 63 ms 6732 KB Output is correct
12 Correct 79 ms 6708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2436 KB Output is correct
2 Correct 17 ms 3028 KB Output is correct
3 Correct 33 ms 3268 KB Output is correct
4 Correct 50 ms 3584 KB Output is correct
5 Correct 67 ms 5460 KB Output is correct
6 Correct 84 ms 5412 KB Output is correct
7 Correct 61 ms 5572 KB Output is correct
8 Correct 78 ms 5468 KB Output is correct
9 Correct 92 ms 5244 KB Output is correct
10 Correct 63 ms 5284 KB Output is correct
11 Correct 57 ms 5232 KB Output is correct
12 Correct 69 ms 5296 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 4612 KB Output is correct
2 Correct 124 ms 4876 KB Output is correct
3 Correct 150 ms 4120 KB Output is correct
4 Correct 130 ms 4504 KB Output is correct
5 Correct 173 ms 6608 KB Output is correct
6 Correct 185 ms 6608 KB Output is correct
7 Correct 132 ms 6600 KB Output is correct
8 Correct 228 ms 6732 KB Output is correct
9 Correct 176 ms 6520 KB Output is correct
10 Correct 199 ms 6604 KB Output is correct
11 Correct 138 ms 6560 KB Output is correct
12 Correct 253 ms 6528 KB Output is correct