Submission #170826

#	Time	Username	Problem	Language	Result	Execution time	Memory
170826		ZwariowanyMarcin	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	298 ms	9252 KiB

sterilizing

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 1e5 + 111;

struct fen {
	ll t[nax];
	
	void init() {
		for(int i = 0; i < nax; ++i)
			t[i] = 0;
	}
	
	void add(int x, int c) {
		for(;x < nax; x += x & -x)
			t[x] += c;
	}
	
	ll query(int x) {
		ll res = 0;
		for(; 0 < x; x -= x & -x)
			res += t[x];
		return res;
	}
	
	ll sum(int l, int r) {
		return query(r) - query(l - 1);
	}
} ja;

set <int> secik;
int n, q, k;
int a[nax];
vector <int> del;

int main() {
	ja.init();
	scanf("%d %d %d", &n, &q, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		secik.insert(i);
		ja.add(i, a[i]);
	}
	for(int i = 1; i <= q; ++i) {
		int type, l, r;
		scanf("%d %d %d", &type, &l, &r);
		if(type == 1) {
			if(!a[l]) secik.insert(l);
			ja.add(l, -a[l]);
			a[l] = r;
			ja.add(l, a[l]);
		}
		if(type == 2) {
			if(k == 1) continue;
			auto it = secik.lower_bound(l);
			while(it != secik.end() && *it <= r) {
				int diff = a[*it] - a[*it] / k;
				ja.add(*it, -diff);
				a[*it] += -diff;
				if(a[*it] == 0)
					del.pb(*it);
				it++;
			}
			for(auto it : del)
				secik.erase(it);
			del.clear();
		}
		if(type == 3) {
			printf("%lld\n", ja.sum(l, r));
		}
	}
				
				
	
	return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &q, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &type, &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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