oj.uz

Submission #70851

# Submission time Handle Problem Language Result Execution time Memory
70851 2018-08-23T14:13:08 Z zadrga Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 956 ms 76052 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);
		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:124: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: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 5 ms 376 KB Output is correct
2 Correct 5 ms 1124 KB Output is correct
3 Correct 5 ms 1732 KB Output is correct
4 Incorrect 11 ms 1732 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 403 ms 38428 KB Output is correct
2 Correct 248 ms 38428 KB Output is correct
3 Correct 328 ms 75388 KB Output is correct
4 Correct 420 ms 75616 KB Output is correct
5 Correct 490 ms 75764 KB Output is correct
6 Correct 537 ms 75992 KB Output is correct
7 Correct 477 ms 75992 KB Output is correct
8 Correct 540 ms 76052 KB Output is correct
9 Correct 422 ms 76052 KB Output is correct
10 Correct 390 ms 76052 KB Output is correct
11 Correct 403 ms 76052 KB Output is correct
12 Correct 398 ms 76052 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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