oj.uz

답안 #70865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70865 2018-08-23T14:34:24 Z zadrga Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 962 ms 84172 KB 
#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:123: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:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", arr + i);
   ~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:131: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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 376 KB Output is correct
2 Correct 6 ms 1180 KB Output is correct
3 Correct 8 ms 1768 KB Output is correct
4 Correct 13 ms 1768 KB Output is correct
5 Correct 18 ms 3000 KB Output is correct
6 Correct 20 ms 3000 KB Output is correct
7 Correct 16 ms 3200 KB Output is correct
8 Correct 16 ms 3324 KB Output is correct
9 Correct 20 ms 3332 KB Output is correct
10 Correct 20 ms 3484 KB Output is correct
11 Correct 20 ms 3484 KB Output is correct
12 Correct 21 ms 3544 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 437 ms 40984 KB Output is correct
2 Correct 318 ms 40984 KB Output is correct
3 Correct 351 ms 78300 KB Output is correct
4 Correct 463 ms 78556 KB Output is correct
5 Correct 608 ms 78556 KB Output is correct
6 Correct 538 ms 78556 KB Output is correct
7 Correct 540 ms 78556 KB Output is correct
8 Correct 633 ms 78564 KB Output is correct
9 Correct 415 ms 78564 KB Output is correct
10 Correct 458 ms 78624 KB Output is correct
11 Correct 436 ms 78624 KB Output is correct
12 Correct 424 ms 78624 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 78624 KB Output is correct
2 Correct 180 ms 78624 KB Output is correct
3 Correct 244 ms 78624 KB Output is correct
4 Correct 497 ms 78624 KB Output is correct
5 Correct 880 ms 81856 KB Output is correct
6 Correct 916 ms 82324 KB Output is correct
7 Correct 532 ms 82324 KB Output is correct
8 Correct 820 ms 82324 KB Output is correct
9 Correct 574 ms 82324 KB Output is correct
10 Correct 580 ms 82324 KB Output is correct
11 Correct 586 ms 82324 KB Output is correct
12 Correct 540 ms 82352 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 505 ms 82352 KB Output is correct
2 Correct 597 ms 82352 KB Output is correct
3 Correct 425 ms 82352 KB Output is correct
4 Correct 597 ms 82352 KB Output is correct
5 Correct 854 ms 84020 KB Output is correct
6 Correct 808 ms 84020 KB Output is correct
7 Correct 874 ms 84020 KB Output is correct
8 Correct 962 ms 84020 KB Output is correct
9 Correct 605 ms 84036 KB Output is correct
10 Correct 536 ms 84108 KB Output is correct
11 Correct 523 ms 84108 KB Output is correct
12 Correct 572 ms 84172 KB Output is correct