oj.uz

Submission #70859

# Submission time Handle Problem Language Result Execution time Memory
70859 2018-08-23T14:26:44 Z zadrga Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 948 ms 78048 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<ll, ll> pii;

ll K;
ll arr[maxn];

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

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

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

		for(ll 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(ll x, ll l, ll d){
		for(ll i = 0; i < logn; i++)
			seg[x][i] = seg[l][i] + seg[d][i];
	}

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

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

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

		ll 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(ll x, ll l, ll d, ll i, ll val){
		push(x, l, d);
		if(l > d || l > i || d < i)
			return;

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

		ll 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(ll x, ll l, ll d, ll i, ll 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;
		}

		ll 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(ll x, ll l, ll d, ll i, ll j){
		push(x, l, d);
		if(l > d || l > j || d < i)
			return 0;

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

		ll 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(){
	ll n, q;
	scanf("%lld%lld%lld", &n, &q, &K);
	for(ll 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:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &n, &q, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", arr + i);
   ~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:133: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 7 ms 472 KB Output is correct
2 Correct 5 ms 1156 KB Output is correct
3 Correct 6 ms 1632 KB Output is correct
4 Incorrect 14 ms 1680 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 405 ms 40244 KB Output is correct
2 Correct 334 ms 40244 KB Output is correct
3 Correct 379 ms 77332 KB Output is correct
4 Correct 393 ms 77700 KB Output is correct
5 Correct 512 ms 77856 KB Output is correct
6 Correct 459 ms 77896 KB Output is correct
7 Correct 475 ms 77924 KB Output is correct
8 Correct 425 ms 77924 KB Output is correct
9 Correct 352 ms 77924 KB Output is correct
10 Correct 474 ms 78048 KB Output is correct
11 Correct 444 ms 78048 KB Output is correct
12 Correct 474 ms 78048 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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