oj.uz

Submission #1117293

# Submission time Handle Problem Language Result Execution time Memory
1117293 2024-11-23T08:43:47 Z Peter2017 Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 530 ms 98632 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) 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 95816 KB Output is correct
2 Incorrect 65 ms 95768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 388 ms 98172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 96336 KB Output is correct
2 Correct 135 ms 96172 KB Output is correct
3 Correct 162 ms 96172 KB Output is correct
4 Correct 324 ms 97096 KB Output is correct
5 Correct 485 ms 97332 KB Output is correct
6 Correct 504 ms 97444 KB Output is correct
7 Incorrect 503 ms 97352 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 97608 KB Output is correct
2 Correct 344 ms 97864 KB Output is correct
3 Correct 241 ms 97096 KB Output is correct
4 Correct 297 ms 97864 KB Output is correct
5 Correct 486 ms 98620 KB Output is correct
6 Correct 449 ms 98632 KB Output is correct
7 Correct 469 ms 98572 KB Output is correct
8 Correct 530 ms 98516 KB Output is correct
9 Correct 373 ms 98376 KB Output is correct
10 Correct 390 ms 98392 KB Output is correct
11 Correct 366 ms 98376 KB Output is correct
12 Correct 361 ms 98388 KB Output is correct