oj.uz

Submission #317289

# Submission time Handle Problem Language Result Execution time Memory
317289 2020-10-29T10:05:29 Z hoangtung_pro Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 363 ms 7932 KB 
#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define bit(s, i) (s & (1<<i))

using namespace std;

const int N = 1e5 + 5;
const int M = 1;
const int K = 1;
const int mod = 1e9+7;
const int inf = 2e9;
const long long Inf = 2e18;

typedef long long ll;
typedef pair < int, int > ii;

int n, q, k, a[N];

struct tree {
	long long sum;
	int ma;
} IT[4 * N];

void reset(int id, int l, int r, int pos) {
	if(l > pos || r < pos) return;

	if(l == r) {
		IT[id].sum = a[pos];
		IT[id].ma = a[pos];
		return;
	}

	int mid = (l + r) >> 1;

	reset(id<<1, l, mid, pos);
	reset(id<<1|1, mid + 1, r, pos);

	IT[id].sum = IT[id<<1].sum + IT[id<<1|1].sum;
	IT[id].ma = max(IT[id<<1].ma, IT[id<<1|1].ma);
}

void div(int id, int l, int r, int u, int v) {
	if(r < u || v < l) return;

	if(l == r) {
		IT[id].ma /= k;
		IT[id].sum /= k;
		return;
	}

	if(IT[id].ma == 0 || k == 1) return;

	int mid = (l + r) >> 1;

	div(id<<1, l, mid, u, v);
	div(id<<1|1, mid + 1, r, u, v);

	IT[id].ma = max(IT[id<<1].ma, IT[id<<1|1].ma);
	IT[id].sum = IT[id<<1].sum + IT[id<<1|1].sum;
}

long long get(int id, int l, int r, int u, int v) {
	if(r < u || v < l) return 0;

	if(u <= l && r <= v) return IT[id].sum;

	int mid = (l + r) >> 1;
	return get(id<<1, l, mid, u, v) + get(id<<1|1, mid + 1, r , u, v);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("trash.inp","r",stdin);
    // freopen("trash.out","w",stdout);

    cin >> n >> q >> k;
    
    for(int i=1;i<=n;++i) {
    	cin >> a[i];
		reset(1, 1, n, i);
	}

	for(int i=1;i<=q;++i) {
		int t, x, y;
		cin >> t >> x >> y;

		if(t == 1) {
			a[x] = y;
			reset(1, 1, n, x);
		}
		if(t == 2) {
			div(1, 1, n, x, y);
		}
		if(t == 3) {
			cout << get(1, 1, n, x, y) << endl;
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 4984 KB Output is correct
2 Correct 62 ms 4668 KB Output is correct
3 Correct 66 ms 6808 KB Output is correct
4 Correct 89 ms 7544 KB Output is correct
5 Correct 99 ms 7800 KB Output is correct
6 Correct 103 ms 7800 KB Output is correct
7 Correct 105 ms 7800 KB Output is correct
8 Correct 101 ms 7932 KB Output is correct
9 Correct 95 ms 7672 KB Output is correct
10 Correct 104 ms 7672 KB Output is correct
11 Correct 93 ms 7672 KB Output is correct
12 Correct 96 ms 7660 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 640 KB Output is correct
2 Correct 24 ms 2816 KB Output is correct
3 Correct 31 ms 2944 KB Output is correct
4 Correct 60 ms 2936 KB Output is correct
5 Correct 103 ms 6392 KB Output is correct
6 Correct 98 ms 6392 KB Output is correct
7 Correct 90 ms 6520 KB Output is correct
8 Correct 101 ms 6392 KB Output is correct
9 Correct 94 ms 6268 KB Output is correct
10 Correct 91 ms 6136 KB Output is correct
11 Correct 91 ms 6136 KB Output is correct
12 Correct 90 ms 6136 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 2780 KB Output is correct
2 Correct 126 ms 4572 KB Output is correct
3 Correct 149 ms 3960 KB Output is correct
4 Correct 152 ms 3576 KB Output is correct
5 Correct 192 ms 7672 KB Output is correct
6 Correct 216 ms 7544 KB Output is correct
7 Correct 189 ms 7544 KB Output is correct
8 Correct 263 ms 7672 KB Output is correct
9 Correct 237 ms 7420 KB Output is correct
10 Correct 273 ms 7684 KB Output is correct
11 Correct 206 ms 7544 KB Output is correct
12 Correct 363 ms 7672 KB Output is correct