oj.uz

Submission #201173

# Submission time Handle Problem Language Result Execution time Memory
201173 2020-02-09T15:05:43 Z quocnguyen1012 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 338 ms 9592 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

struct node
{
  ll sum;
  int Max, pos;
  node(ll sum = 0, int Max = 0, int pos = 0):
    sum(sum), Max(Max), pos(pos) {}
  node operator + (const node & other) const
  {
    node res; res.sum = sum + other.sum;
    res.Max = max(Max, other.Max);
    res.pos = (Max < other.Max) ? other.pos : pos;
    return res;
  }
}ST[4 * maxn];
int N, Q, K;

#define lc id << 1
#define rc id << 1 | 1

void build(int id, int l, int r)
{
  if (l == r){
    ST[id].pos = l;
    return;
  }
  int mid = (l + r) / 2;
  build(lc, l, mid); build(rc, mid + 1, r);
}

void update(int id, int l, int r, int i, int val)
{
  if (r < i || l > i) return;
  if (l == r){
    ST[id].Max = ST[id].sum = val;
    return;
  }
  int mid = (l + r) / 2;
  update(lc, l, mid, i, val); update(rc, mid + 1, r, i, val);
  ST[id] = ST[lc] + ST[rc];
}

void rupd(int id, int l, int r ,int L, int R)
{
  if (l > R || L > r || ST[id].Max == 0){
    return;
  }
  if (l == r){
    ST[id].Max = ST[id].sum = ST[id].Max / K;
    return;
  }
  int mid = (l + r) / 2;
  rupd(lc, l, mid, L, R); rupd(rc, mid + 1, r, L, R);
  ST[id] = ST[lc] + ST[rc];
}

node query(int id, int l, int r, int L, int R)
{
  if (L <= l && r <= R){
    return ST[id];
  }
  if (L > r || l > R) return node(0, -1e9);
  int mid = (l + r) / 2;
  return query(lc, l, mid, L, R) + query(rc, mid + 1, r, L, R);
}
#undef lc
#undef rc

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> Q >> K;
  build(1, 1, N);
  for (int i = 1; i <= N; ++i){
    int x; cin >> x;
    update(1, 1, N, i, x);
  }
  for (int i = 1; i <= Q; ++i){
    int type; cin >> type;
    if (type == 1){
      int pos, val; cin >> pos >> val;
      update(1 ,1, N, pos, val);
    }
    else if (type == 2){
      int l, r; cin >> l >> r;
      if (K != 1) rupd(1, 1, N, l, r);
    }
    else{
      int l, r; cin >> l >> r;
      cout << query(1, 1, N, l, r).sum << '\n';
    }
  }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:84:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:85:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6648 KB Output is correct
2 Correct 8 ms 6648 KB Output is correct
3 Correct 11 ms 6520 KB Output is correct
4 Correct 12 ms 6648 KB Output is correct
5 Correct 13 ms 6648 KB Output is correct
6 Correct 12 ms 6648 KB Output is correct
7 Correct 12 ms 6648 KB Output is correct
8 Correct 12 ms 6648 KB Output is correct
9 Correct 13 ms 6648 KB Output is correct
10 Correct 12 ms 6648 KB Output is correct
11 Correct 14 ms 6776 KB Output is correct
12 Correct 13 ms 6648 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 7416 KB Output is correct
2 Correct 77 ms 8696 KB Output is correct
3 Correct 78 ms 8528 KB Output is correct
4 Correct 97 ms 9080 KB Output is correct
5 Correct 104 ms 9592 KB Output is correct
6 Correct 110 ms 9588 KB Output is correct
7 Correct 117 ms 9592 KB Output is correct
8 Correct 111 ms 9592 KB Output is correct
9 Correct 102 ms 9440 KB Output is correct
10 Correct 103 ms 9464 KB Output is correct
11 Correct 103 ms 9440 KB Output is correct
12 Correct 107 ms 9464 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6652 KB Output is correct
2 Correct 31 ms 6648 KB Output is correct
3 Correct 35 ms 6648 KB Output is correct
4 Correct 66 ms 6648 KB Output is correct
5 Correct 99 ms 6648 KB Output is correct
6 Correct 101 ms 6648 KB Output is correct
7 Correct 100 ms 7284 KB Output is correct
8 Correct 102 ms 8056 KB Output is correct
9 Correct 93 ms 7928 KB Output is correct
10 Correct 98 ms 7928 KB Output is correct
11 Correct 108 ms 7936 KB Output is correct
12 Correct 89 ms 7928 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 6776 KB Output is correct
2 Correct 132 ms 6880 KB Output is correct
3 Correct 150 ms 6904 KB Output is correct
4 Correct 158 ms 6904 KB Output is correct
5 Correct 205 ms 6904 KB Output is correct
6 Correct 222 ms 6904 KB Output is correct
7 Correct 182 ms 6904 KB Output is correct
8 Correct 257 ms 6904 KB Output is correct
9 Correct 244 ms 6904 KB Output is correct
10 Correct 260 ms 6904 KB Output is correct
11 Correct 199 ms 6904 KB Output is correct
12 Correct 338 ms 6904 KB Output is correct