oj.uz

Submission #1117294

# Submission time Handle Problem Language Result Execution time Memory
1117294 2024-11-23T08:46:43 Z Peter2017 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 501 ms 98744 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pill pair<int,ll>
#define mem(a, b) memset(a, b, sizeof(a))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define name "test"

using namespace std;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int MAX = 1e9;
const int LOG = 31 - __builtin_clz(MAX);

template <typename T1, typename T2> bool maxi(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;}
template <typename T1, typename T2> bool mini(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;}

int n;
int q;
int k;

struct SEGTREE
{
	struct Node{
		ll v[LOG + 1];
		Node(){mem(v, 0);}
		friend Node operator + (Node A, Node B){
			for (int j = 0; j <= LOG; j++)
				A.v[j] += B.v[j];
			return A;
		}
		Node update(int k){
			Node res;
			Node A = (*this);
			for (int j = 0; j <= LOG; j++){
				if (j + k > LOG) res.v[j] = 0;
				else res.v[j] = A.v[j + k];
			}
			return res;
		}
	};

	int lz[N << 2];
	Node val[N << 2];

	SEGTREE(){};

	void down(int id, int l, int r){
		if (!lz[id]) return;
		val[id] = val[id].update(lz[id]);
		if (l < r){
			lz[id << 1] += lz[id];
			lz[id << 1 | 1] += lz[id];
		}
		lz[id] = 0;
	}

	void updatePoint(int id, int l, int r, int i, int x){
		down(id, l, r);
		if (l > i || r < i) return;
		if (l == r){
			for (int j = 0; j <= LOG; j++){
				val[id].v[j] = x;
				x /= k;
			}
			return;
		}
		int m = (l + r) >> 1;
		updatePoint(id << 1, l, m, i, x);
		updatePoint(id << 1 | 1, m + 1, r, i, x);
		val[id] = val[id << 1] + val[id << 1 | 1];
	}


	void updateRange(int id, int l, int r, int u, int v){
		down(id, l, r);
		if (l > v || r < u) return;
		if (l >= u && r <= v){
			lz[id]++;
			down(id, l, r);
			return;
		}
		int m = (l + r) >> 1;
		updateRange(id << 1, l, m, u, v);
		updateRange(id << 1 | 1, m + 1, r, u, v);
		val[id] = val[id << 1] + val[id << 1 | 1];
	}

	ll get(int id, int l, int r, int u, int v){
		down(id, l, r);
		if (l > v || r < u) return 0;
		if (l >= u && r <= v) return val[id].v[0];
		int m = (l + r) >> 1;
		return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
	}
} ST;

void load(){
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
}

void input(){
	cin >> n >> q >> k;
	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		ST.updatePoint(1, 1, n, i, x);
	}
}

void solve(){
	while (q--){
		int type, a, b; cin >> type >> a >> b;
		if (type == 1) ST.updatePoint(1, 1, n, a, b);
		if (type == 2 && k != 1) ST.updateRange(1, 1, n, a, b);
		if (type == 3) cout << ST.get(1, 1, n, a, b) << '\n';
	}
}

int main(){
    load();
    input();
    solve();
}

Compilation message

sterilizing.cpp: In function 'void load()':
sterilizing.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 95688 KB Output is correct
2 Correct 57 ms 95556 KB Output is correct
3 Correct 57 ms 95628 KB Output is correct
4 Correct 62 ms 95680 KB Output is correct
5 Correct 63 ms 95816 KB Output is correct
6 Correct 65 ms 95816 KB Output is correct
7 Correct 63 ms 95848 KB Output is correct
8 Correct 67 ms 95816 KB Output is correct
9 Correct 76 ms 95816 KB Output is correct
10 Correct 73 ms 95796 KB Output is correct
11 Correct 67 ms 95824 KB Output is correct
12 Correct 67 ms 95816 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 96132 KB Output is correct
2 Correct 133 ms 97804 KB Output is correct
3 Correct 162 ms 97608 KB Output is correct
4 Correct 208 ms 98120 KB Output is correct
5 Correct 219 ms 98668 KB Output is correct
6 Correct 227 ms 98744 KB Output is correct
7 Correct 225 ms 98632 KB Output is correct
8 Correct 215 ms 98632 KB Output is correct
9 Correct 211 ms 98376 KB Output is correct
10 Correct 218 ms 98376 KB Output is correct
11 Correct 215 ms 98376 KB Output is correct
12 Correct 206 ms 98376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 95816 KB Output is correct
2 Correct 149 ms 95816 KB Output is correct
3 Correct 162 ms 95816 KB Output is correct
4 Correct 331 ms 95972 KB Output is correct
5 Correct 474 ms 95972 KB Output is correct
6 Correct 483 ms 96000 KB Output is correct
7 Correct 217 ms 95844 KB Output is correct
8 Correct 497 ms 97352 KB Output is correct
9 Correct 382 ms 97152 KB Output is correct
10 Correct 363 ms 97280 KB Output is correct
11 Correct 390 ms 97272 KB Output is correct
12 Correct 365 ms 97124 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 95960 KB Output is correct
2 Correct 322 ms 95968 KB Output is correct
3 Correct 229 ms 96072 KB Output is correct
4 Correct 332 ms 96080 KB Output is correct
5 Correct 473 ms 96044 KB Output is correct
6 Correct 474 ms 96048 KB Output is correct
7 Correct 478 ms 96072 KB Output is correct
8 Correct 501 ms 96088 KB Output is correct
9 Correct 378 ms 96072 KB Output is correct
10 Correct 351 ms 97412 KB Output is correct
11 Correct 379 ms 96072 KB Output is correct
12 Correct 400 ms 96312 KB Output is correct