Submission #231392

#	Time	Username	Problem	Language	Result	Execution time	Memory
231392		AlexLuchianov	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	265 ms	9516 KiB

sterilizing

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <set>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int v[1 + nmax];

class FenwickTree{
private:
  vector<ll> aib;
  int n;
public:
  FenwickTree(int n_ = 0){
    n = n_;
    aib.resize(1 + n);
  }
  void update(int pos, int val){
    for(int x = pos; x <= n; x += (x ^ (x & (x - 1))))
      aib[x] += val;
  }
  ll query(int pos){
    ll result = 0;
    for(int x = pos; 0 < x; x = (x & (x - 1)))
      result += aib[x];
    return result;
  }

  ll _query(int x, int y){
    ll result = query(y);
    if(0 < x)
      result -= query(x - 1);
    return result;
  }
};
FenwickTree aib;

set<int> myset;

void setvalue(int pos, int val){
  aib.update(pos, val - v[pos]);
  v[pos] = val;
  if(0 == v[pos])
    myset.erase(pos);
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, q, k;
  cin >> n >> q >> k;
  aib = FenwickTree(1 + n);
  for(int i = 1;i <= n; i++){
    int val;
    cin >> val;
    setvalue(i, val);
    myset.insert(i);
  }
  for(int i = 1;i <= q; i++){
    int op, x, y;
    cin >> op >> x >> y;
    if(op == 1){
      myset.insert(x);
      setvalue(x, y);
    } else if(op == 2){
      if(k == 1)
        continue;
      vector<int> targets;
      for(set<int>::iterator it = myset.lower_bound(x); it != myset.end() && *it <= y; it++)
        targets.push_back(*it);
      for(int i = 0; i < targets.size(); i++)
        setvalue(targets[i], v[targets[i]] / k);
    } else {
      cout << aib._query(x, y) << '\n';
    }
  }
  return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:81:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < targets.size(); i++)
                      ~~^~~~~~~~~~~~~~~~

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