oj.uz

Submission #70861

# Submission time Handle Problem Language Result Execution time Memory
70861 2018-08-23T14:30:01 Z zadrga Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 959 ms 112692 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;

		lazy[x] = min(lazy[x], 1LL * logn);

		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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 5 ms 1000 KB Output is correct
3 Correct 6 ms 1604 KB Output is correct
4 Correct 12 ms 1660 KB Output is correct
5 Correct 17 ms 3032 KB Output is correct
6 Correct 15 ms 3132 KB Output is correct
7 Correct 18 ms 3132 KB Output is correct
8 Correct 18 ms 3292 KB Output is correct
9 Correct 16 ms 3520 KB Output is correct
10 Correct 16 ms 3520 KB Output is correct
11 Correct 17 ms 3600 KB Output is correct
12 Correct 21 ms 3600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 39104 KB Output is correct
2 Correct 291 ms 39104 KB Output is correct
3 Correct 337 ms 76104 KB Output is correct
4 Correct 435 ms 76356 KB Output is correct
5 Correct 590 ms 76452 KB Output is correct
6 Correct 590 ms 76588 KB Output is correct
7 Correct 545 ms 76588 KB Output is correct
8 Correct 509 ms 76588 KB Output is correct
9 Correct 443 ms 76588 KB Output is correct
10 Correct 405 ms 76588 KB Output is correct
11 Correct 393 ms 76588 KB Output is correct
12 Correct 476 ms 76588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 76588 KB Output is correct
2 Correct 163 ms 76588 KB Output is correct
3 Correct 242 ms 76588 KB Output is correct
4 Correct 585 ms 76588 KB Output is correct
5 Correct 959 ms 79484 KB Output is correct
6 Correct 815 ms 80860 KB Output is correct
7 Correct 548 ms 82368 KB Output is correct
8 Correct 932 ms 83752 KB Output is correct
9 Correct 516 ms 84956 KB Output is correct
10 Correct 541 ms 86260 KB Output is correct
11 Correct 605 ms 87596 KB Output is correct
12 Correct 601 ms 88740 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 88740 KB Output is correct
2 Correct 611 ms 88740 KB Output is correct
3 Correct 402 ms 88740 KB Output is correct
4 Correct 516 ms 88740 KB Output is correct
5 Correct 822 ms 96224 KB Output is correct
6 Correct 791 ms 98668 KB Output is correct
7 Correct 878 ms 100864 KB Output is correct
8 Correct 918 ms 103484 KB Output is correct
9 Correct 583 ms 106020 KB Output is correct
10 Correct 576 ms 108144 KB Output is correct
11 Correct 582 ms 110376 KB Output is correct
12 Correct 490 ms 112692 KB Output is correct