Submission #201173

#	Time	Username	Problem	Language	Result	Execution time	Memory
201173		quocnguyen1012	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	338 ms	9592 KiB

sterilizing

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75