oj.uz

Submission #372358

# Submission time Handle Problem Language Result Execution time Memory
372358 2021-02-27T20:40:29 Z LucaDantas Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 224 ms 5740 KB 
#include<bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e5+10;

struct SegmentTree
{
	long long tree[4*maxn]; int k, a[maxn];
	void build(int node, int i, int j) {
		if(i == j) return (void)(tree[node] = a[i]);
		int m = (i+j) >> 1;
		build(2*node, i, m); build(2*node+1, m+1, j);
		tree[node] = tree[2*node] + tree[2*node+1];
	}
	void upd(int node, int i, int j, int pos, int v) {
		if(i == j) return (void)(tree[node] = v);
		int m = (i+j) >> 1;
		if(pos <= m) upd(2*node, i, m, pos, v);
		else upd(2*node+1, m+1, j, pos, v);
		tree[node] = tree[2*node] + tree[2*node+1];
	}
	void apply(int node, int i, int j, int l, int r) {
		if(i > r || j < l || !tree[node]) return;
		if(i == j) return (void)(tree[node] /= k);
		int m = (i+j) >> 1;
		apply(2*node, i, m, l, r);
		apply(2*node+1, m+1, j, l, r);
		tree[node] = tree[2*node] + tree[2*node+1];
	}
	long long query(int node, int i, int j, int l, int r) {
		if(i > r || j < l) return 0ll;
		if(i >= l && j <= r) return tree[node];
		int m = (i+j) >> 1;
		return query(2*node, i, m, l, r) + query(2*node+1, m+1, j, l, r);
	}
} seg;

int main() {
	int n, q, k; scanf("%d %d %d", &n, &q, &k); seg.k = k;
	for(int i = 1; i <= n; i++)
		scanf("%d", &seg.a[i]);
	seg.build(1, 1, n);
	while(q--) {
		int s, a, b; scanf("%d %d %d", &s, &a, &b);
		if(s == 1) seg.upd(1, 1, n, a, b);
		if(s == 2 && k > 1) seg.apply(1, 1, n, a, b);
		if(s == 3) printf("%lld\n", seg.query(1, 1, n, a, b));
	}
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:39:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  int n, q, k; scanf("%d %d %d", &n, &q, &k); seg.k = k;
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |   scanf("%d", &seg.a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:44:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |   int s, a, b; scanf("%d %d %d", &s, &a, &b);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3948 KB Output is correct
2 Correct 53 ms 3692 KB Output is correct
3 Correct 48 ms 4716 KB Output is correct
4 Correct 59 ms 5228 KB Output is correct
5 Correct 74 ms 5740 KB Output is correct
6 Correct 74 ms 5740 KB Output is correct
7 Correct 71 ms 5740 KB Output is correct
8 Correct 71 ms 5740 KB Output is correct
9 Correct 67 ms 5612 KB Output is correct
10 Correct 68 ms 5612 KB Output is correct
11 Correct 67 ms 5612 KB Output is correct
12 Correct 72 ms 5516 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1004 KB Output is correct
2 Correct 15 ms 1772 KB Output is correct
3 Correct 20 ms 1900 KB Output is correct
4 Correct 53 ms 2156 KB Output is correct
5 Correct 68 ms 4204 KB Output is correct
6 Correct 68 ms 4204 KB Output is correct
7 Correct 65 ms 4352 KB Output is correct
8 Correct 68 ms 4204 KB Output is correct
9 Correct 67 ms 4076 KB Output is correct
10 Correct 70 ms 4076 KB Output is correct
11 Correct 68 ms 4204 KB Output is correct
12 Correct 64 ms 4076 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 3308 KB Output is correct
2 Correct 90 ms 3520 KB Output is correct
3 Correct 97 ms 2924 KB Output is correct
4 Correct 111 ms 3012 KB Output is correct
5 Correct 133 ms 5484 KB Output is correct
6 Correct 156 ms 5612 KB Output is correct
7 Correct 127 ms 5612 KB Output is correct
8 Correct 171 ms 5612 KB Output is correct
9 Correct 153 ms 5484 KB Output is correct
10 Correct 170 ms 5356 KB Output is correct
11 Correct 131 ms 5356 KB Output is correct
12 Correct 224 ms 5484 KB Output is correct