oj.uz

Submission #389371

# Submission time Handle Problem Language Result Execution time Memory
389371 2021-04-14T03:43:01 Z VROOM_VARUN Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 176 ms 9488 KB 
/*
ID: varunra2
LANG: C++
TASK: spray
*/

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define int long long

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

struct fenwick {
  VI bit;
  int n;
  void init(int _n) {
    n = _n;
    bit.resize(n + 1, 0);
  }

  int qry(int ind) {
    int ret = 0;
    ind++;
    while (ind > 0) {
      ret += bit[ind];
      ind -= (ind & -ind);
    }
    return ret;
  }

  void upd(int ind, int val) {
    ind++;
    while (ind <= n) {
      bit[ind] += val;
      ind += (ind & -ind);
    }
  }

  int qry(int l, int r) { return qry(r) - qry(l - 1); }
};

int32_t main() {
  // #ifndef ONLINE_JUDGE
  // freopen("spray.in", "r", stdin);
  // freopen("spray.out", "w", stdout);
  // #endif
  cin.sync_with_stdio(0);
  cin.tie(0);

  int n, q, k;
  cin >> n >> q >> k;
  VI vals(n);

  trav(x, vals) cin >> x;

  SETI use;

  rep(i, 0, n) if (vals[i] > 0) use.insert(i);

  fenwick bit;

  bit.init(n);

  for (int i = 0; i < n; i++) {
    bit.upd(i, vals[i]);
  }

  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int a, b;
      cin >> a >> b;
      a--;
      bit.upd(a, b - vals[a]);
      if (vals[a] == 0 and b > 0) {
        use.insert(a);
      }
      if (b == 0 and vals[a] > 0) {
        use.erase(use.find(a));
      }
      vals[a] = b;
    } else if (type == 2) {
      int l, r;
      cin >> l >> r;
      if (k == 1) continue;
      l--, r--;
      auto it = use.lower_bound(l);
      while (it != use.end()) {
        int ind = *it;
        if (ind > r) break;
        bit.upd(ind, vals[ind] / k - vals[ind]);
        vals[ind] /= k;
        it++;
        if (vals[ind] == 0) {
          SETI::iterator prv = it;
          prv--;
          use.erase(prv);
        }
      }
    } else {
      int l, r;
      cin >> l >> r;
      l--, r--;
      cout << bit.qry(l, r) << '\n';
    }
  }

  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 4 ms 588 KB Output is correct
10 Correct 4 ms 592 KB Output is correct
11 Correct 4 ms 460 KB Output is correct
12 Correct 4 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5628 KB Output is correct
2 Correct 43 ms 4448 KB Output is correct
3 Correct 49 ms 7080 KB Output is correct
4 Correct 60 ms 8944 KB Output is correct
5 Correct 67 ms 9420 KB Output is correct
6 Correct 69 ms 9488 KB Output is correct
7 Correct 67 ms 9460 KB Output is correct
8 Correct 67 ms 9408 KB Output is correct
9 Correct 67 ms 9316 KB Output is correct
10 Correct 66 ms 9284 KB Output is correct
11 Correct 68 ms 9352 KB Output is correct
12 Correct 66 ms 9284 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1020 KB Output is correct
2 Correct 19 ms 2320 KB Output is correct
3 Correct 22 ms 2464 KB Output is correct
4 Correct 46 ms 2424 KB Output is correct
5 Correct 60 ms 5624 KB Output is correct
6 Correct 58 ms 5672 KB Output is correct
7 Correct 57 ms 5760 KB Output is correct
8 Correct 63 ms 5676 KB Output is correct
9 Correct 54 ms 5536 KB Output is correct
10 Correct 58 ms 5512 KB Output is correct
11 Correct 52 ms 5548 KB Output is correct
12 Correct 52 ms 5496 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5236 KB Output is correct
2 Correct 74 ms 5600 KB Output is correct
3 Correct 86 ms 4384 KB Output is correct
4 Correct 76 ms 4248 KB Output is correct
5 Correct 115 ms 9188 KB Output is correct
6 Correct 128 ms 9284 KB Output is correct
7 Correct 118 ms 9452 KB Output is correct
8 Correct 153 ms 9280 KB Output is correct
9 Correct 126 ms 9140 KB Output is correct
10 Correct 163 ms 9220 KB Output is correct
11 Correct 122 ms 9284 KB Output is correct
12 Correct 176 ms 9152 KB Output is correct