oj.uz

Submission #444781

# Submission time Handle Problem Language Result Execution time Memory
444781 2021-07-15T09:19:39 Z wind_reaper Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 231 ms 5688 KB 
#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/

using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//***************** CONSTANTS *****************



//***************** GLOBAL VARIABLES *****************



//***************** AUXILIARY STRUCTS *****************

struct SegmentTree{
	vector<int64_t> tree;
	int sz = 1;

	SegmentTree(int N, vector<int>& A){
		while(sz < N)
			sz <<= 1;
		tree.resize(2*sz);
		build(A, 0, 0, sz);
	}

	void build(vector<int>& A, int x, int lx, int rx){
		if(rx - lx == 1){
			if(lx < A.size())
				tree[x] = A[lx];
			return;
		}

		int mid = (lx + rx) >> 1;
		build(A, 2*x + 1, lx, mid);
		build(A, 2*x + 2, mid, rx);

		tree[x] = tree[2*x + 1] + tree[2*x + 2]; 
	}

	void update(int val, int idx, int x, int lx, int rx){
		if(rx - lx == 1){
			tree[x] = val;
			return;
		}

		int mid = (lx + rx) >> 1;
		if(idx < mid) update(val, idx, 2*x + 1, lx, mid);
		else update(val, idx, 2*x + 2, mid, rx);

		tree[x] = tree[2*x + 1] + tree[2*x + 2];
	}

	void update(int val, int idx) { update(val, idx, 0, 0, sz); }

	void spray(int K, int l, int r, int x, int lx, int rx){
		if(rx <= l || lx >= r || tree[x] == 0)
			return;
		if(rx - lx == 1){
			tree[x] /= K;
			return;
		}

		int mid = (lx + rx) >> 1;
		spray(K, l, r, 2*x + 1, lx, mid);
		spray(K, l, r, 2*x + 2, mid, rx);

		tree[x] = tree[2*x + 1] + tree[2*x + 2];
	}

	void spray(int K, int l, int r) { spray(K, l, r, 0, 0, sz); }

	int64_t query(int l, int r, int x, int lx, int rx){
		if(rx <= l || lx >= r || tree[x] == 0)
			return 0;
		if(lx >= l && rx <= r)
			return tree[x];

		int mid = (lx + rx) >> 1;
		return query(l, r, 2*x + 1, lx, mid) + query(l, r, 2*x + 2, mid, rx);
	}

	int64_t query(int l, int r) { return query(l, r, 0, 0, sz); }
};

//***************** MAIN BODY *****************

void solve(){
	int N, Q, K;
	cin >> N >> Q >> K;

	vector<int> A(N);

	for(int i = 0; i < N; i++)
		cin >> A[i];

	SegmentTree S(N, A);

	while(Q--){
		int type, l, r;
		cin >> type >> l >> r;
		if(type == 1){
			S.update(r, l - 1);
		}
		if(type == 2){
			if(K > 1) S.spray(K, l - 1, r);
		}
		if(type == 3){
			cout << S.query(l - 1, r) << '\n';
		}
	}
}

//***************** *****************

int32_t main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif

	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++)
		solve();

	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif

	return 0;
}

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic
*/

Compilation message

sterilizing.cpp: In member function 'void SegmentTree::build(std::vector<int>&, int, int, int)':
sterilizing.cpp:39:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    if(lx < A.size())
      |       ~~~^~~~~~~~~~

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 1 ms 332 KB Output is correct
4 Correct 4 ms 332 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 4 ms 460 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 53 ms 3780 KB Output is correct
2 Correct 48 ms 3516 KB Output is correct
3 Correct 42 ms 4584 KB Output is correct
4 Correct 54 ms 5192 KB Output is correct
5 Correct 66 ms 5572 KB Output is correct
6 Correct 64 ms 5584 KB Output is correct
7 Correct 65 ms 5688 KB Output is correct
8 Correct 68 ms 5580 KB Output is correct
9 Correct 67 ms 5444 KB Output is correct
10 Correct 67 ms 5488 KB Output is correct
11 Correct 60 ms 5552 KB Output is correct
12 Correct 63 ms 5444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 948 KB Output is correct
2 Correct 12 ms 1816 KB Output is correct
3 Correct 16 ms 1900 KB Output is correct
4 Correct 43 ms 2084 KB Output is correct
5 Correct 53 ms 4148 KB Output is correct
6 Correct 53 ms 4164 KB Output is correct
7 Correct 57 ms 4312 KB Output is correct
8 Correct 54 ms 4172 KB Output is correct
9 Correct 53 ms 4036 KB Output is correct
10 Correct 53 ms 4072 KB Output is correct
11 Correct 51 ms 4060 KB Output is correct
12 Correct 52 ms 4056 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3140 KB Output is correct
2 Correct 88 ms 3380 KB Output is correct
3 Correct 108 ms 2792 KB Output is correct
4 Correct 112 ms 2928 KB Output is correct
5 Correct 123 ms 5444 KB Output is correct
6 Correct 141 ms 5444 KB Output is correct
7 Correct 119 ms 5452 KB Output is correct
8 Correct 166 ms 5424 KB Output is correct
9 Correct 154 ms 5320 KB Output is correct
10 Correct 179 ms 5552 KB Output is correct
11 Correct 128 ms 5308 KB Output is correct
12 Correct 231 ms 5300 KB Output is correct