oj.uz

Submission #70855

# Submission time Handle Problem Language Result Execution time Memory
70855 2018-08-23T14:17:41 Z zadrga Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 986 ms 75944 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)
			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);
		combine(x, 2 * x, 2 * x + 1);
		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 376 KB Output is correct
2 Correct 5 ms 996 KB Output is correct
3 Correct 6 ms 1728 KB Output is correct
4 Incorrect 16 ms 1728 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 449 ms 38524 KB Output is correct
2 Correct 340 ms 38524 KB Output is correct
3 Correct 363 ms 75368 KB Output is correct
4 Correct 510 ms 75812 KB Output is correct
5 Correct 653 ms 75812 KB Output is correct
6 Correct 659 ms 75940 KB Output is correct
7 Correct 584 ms 75940 KB Output is correct
8 Correct 601 ms 75944 KB Output is correct
9 Correct 428 ms 75944 KB Output is correct
10 Correct 426 ms 75944 KB Output is correct
11 Correct 414 ms 75944 KB Output is correct
12 Correct 445 ms 75944 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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