oj.uz

Submission #70846

# Submission time Handle Problem Language Result Execution time Memory
70846 2018-08-23T14:10:31 Z zadrga Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 926 ms 99424 KB 
// 15.22

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 100111
#define logn 35

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

ll K;
ll arr[maxn];

struct segtree{
	ll seg[4 * maxn][logn];
	int lazy[4 * maxn];

	void push(int x, int l, int d){
		if(lazy[x] == 0 || K == 1)
			return;

		int k = lazy[x];
		for(int i = 0; i + k < logn; i++)
			seg[x][i] = seg[x][i + k];

		for(int i = logn - k; i < logn; i++)
			seg[x][i] = 0;

		if(l != d){
			lazy[2 * x] += lazy[x];
			lazy[2 * x + 1] += lazy[x];
		}
		lazy[x] = 0;
	}

	void combine(int x, int l, int d){
		for(int i = 0; i < logn; i++)
			seg[x][i] = seg[l][i] + seg[d][i];
	}

	void setValue(int x, ll val){
		seg[x][0] = val;
		for(int i = 1; i < logn; i++)
			seg[x][i] = seg[x][i - 1] / K;
	}

	void build(int x, int l, int d){
		if(l > d)
			return;

		if(l == d){
			setValue(x, arr[l]);
			lazy[x] = 0;
			return;
		}

		int mid = (l + d) / 2;
		build(2 * x, l, mid);
		build(2 * x + 1, mid + 1, d);
		combine(x, 2 * x, 2 * x + 1);
		lazy[x] = 0;
	}

	void update(int x, int l, int d, int i, ll val){
		push(x, l, d);
		if(l > d || l > i || d < i)
			return;

		if(l == d && l == i){
			setValue(x, val);
			return;
		}

		int mid = (l + d) / 2;
		update(2 * x, l, mid, i, val);
		update(2 * x + 1, mid + 1, d, i, val);
		combine(x, 2 * x, 2 * x + 1);
	}


	void reduce(int x, int l, int d, int i, int j){
		push(x, l, d);
		if(l > d || l > j || d < i)
			return;

		if(i <= l && d <= j){
			lazy[x] += 1;
			push(x, l, d);
			return;
		}

		int mid = (l + d) / 2;
		reduce(2 * x, l, mid, i, j);
		reduce(2 * x + 1, mid + 1, d, i, j);
		combine(x, 2 * x, 2 * x + 1);
	}

	ll query(int x, int l, int d, int i, int j){
		push(x, l, d);
		if(l > d || l > j || d < i)
			return 0;

		if(i <= l && d <= j)
			return seg[x][0];

		int mid = (l + d) / 2;
		ll ret = query(2 * x, l, mid, i, j);
		ret += query(2 * x + 1, mid + 1, d, i, j);
		return ret;
	}
}seg;

int main(){
	int n, q;
	scanf("%d%d%lld", &n, &q, &K);
	for(int i = 1; i <= n; i++)
		scanf("%lld", arr + i);

	seg.build(1, 1, n);

	while(q--){
		ll t, x, y;
		scanf("%lld%lld%lld", &t, &x, &y);

		if(t == 1)
			seg.update(1, 1, n, x, y);
		
		if(t == 2)
			seg.reduce(1, 1, n, x, y);

		if(t == 3)
			printf("%lld\n", seg.query(1, 1, n, x, y));
	}
	
	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &n, &q, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", arr + i);
   ~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &t, &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 1128 KB Output is correct
3 Correct 6 ms 1740 KB Output is correct
4 Incorrect 10 ms 1740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 37932 KB Output is correct
2 Correct 257 ms 37932 KB Output is correct
3 Correct 317 ms 77788 KB Output is correct
4 Correct 436 ms 80288 KB Output is correct
5 Correct 492 ms 82840 KB Output is correct
6 Correct 488 ms 85188 KB Output is correct
7 Correct 471 ms 87556 KB Output is correct
8 Correct 503 ms 90236 KB Output is correct
9 Correct 430 ms 92584 KB Output is correct
10 Correct 377 ms 94688 KB Output is correct
11 Correct 434 ms 97104 KB Output is correct
12 Correct 419 ms 99424 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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