oj.uz

Submission #187597

# Submission time Handle Problem Language Result Execution time Memory
187597 2020-01-13T03:42:50 Z dndhk Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 773 ms 54312 KB 
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 100000;
const ll INFLL = 10000;
const int MAX_K = 30;

int N, Q;
ll K;
ll C[MAX_N+1];

struct SEG{
	struct NODE{
		int l, r;
		ll d[MAX_K];
		int lazy;
	};
	NODE seg[MAX_N*2+1];
	int SZ, cnt=0;
	void add(){
		seg[cnt].l = seg[cnt].r = -1;
		seg[cnt].lazy = 0;
		cnt++;
	}
	void Init(int x){
		SZ =x ;
		add();
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e){
			seg[idx].d[0] = C[s];
			for(int i=1; i<MAX_K; i++){
				seg[idx].d[i] = seg[idx].d[i-1]/K;
			}
			return;
		}
		seg[idx].l = cnt; add();
		seg[idx].r = cnt; add();
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
		for(int i=0; i<MAX_K; i++){
			seg[idx].d[i] = seg[seg[idx].l].d[i]+seg[seg[idx].r].d[i];
		}
	}

	void shift(int idx, int k){
		for(int i=0; i<MAX_K; i++){
			if(i+k<MAX_K){
				seg[idx].d[i] = seg[idx].d[i+k];
			}else{
				seg[idx].d[i] = 0;
			}
		}
	}
	void calc(int idx){
		if(seg[idx].l!=-1 && seg[idx].lazy!=0){
			if(K==1){
				seg[idx].lazy = 0;
				return;
			}
			shift(seg[idx].l, seg[idx].lazy);
			shift(seg[idx].r, seg[idx].lazy);
			seg[seg[idx].l].lazy+=seg[idx].lazy;
			seg[seg[idx].r].lazy+=seg[idx].lazy;
			seg[idx].lazy = 0;
		}
	}
	void Update(int x, ll y){
		update(0, 1, SZ, x, y);
	}
	void update(int idx, int s, int e, int x, ll y){
		calc(idx);
		if(s==e){
			seg[idx].d[0] = y;
			for(int i=1; i<MAX_K; i++){
				seg[idx].d[i] = seg[idx].d[i-1]/K;
			}
			return;
		}
		if(x<=(s+e)/2){
			update(seg[idx].l, s, (s+e)/2, x, y);
		}else{
			update(seg[idx].r, (s+e)/2+1, e, x, y);
		}
		for(int i=0; i<MAX_K; i++){
			seg[idx].d[i] = seg[seg[idx].l].d[i]+seg[seg[idx].r].d[i];
		}
	}
	void Lazy(int x, int y){
		lazy(0, 1, SZ, x, y);
	}
	void lazy(int idx, int s, int e, int x, int y){
		calc(idx);
		if(x<=s && e<=y){
			if(K==1)	return;
			for(int i=0; i<MAX_K-1; i++){
				seg[idx].d[i] = seg[idx].d[i+1];
			}
			seg[idx].d[MAX_K-1] = 0;
			seg[idx].lazy++;
			return;
		}if(x>e || y<s)	return;
		lazy(seg[idx].l, s, (s+e)/2, x, y);
		lazy(seg[idx].r, (s+e)/2+1, e, x, y);
		for(int i=0; i<MAX_K; i++){
			seg[idx].d[i] = seg[seg[idx].l].d[i]+seg[seg[idx].r].d[i];
		}
	}
	ll Sum(int x, int y){
		return sum(0, 1, SZ, x, y);
	}
	ll sum(int idx, int s, int e, int x, int y){
		calc(idx);
		if(x<=s && e<=y)	return seg[idx].d[0];
		if(x>e || y<s)	return 0LL;
		return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
	}
}Seg;

int main(){
	scanf("%d%d%lld", &N, &Q, &K);
	for(int i =1; i<=N; i++){
		scanf("%lld", &C[i]);
	}
	Seg.Init(N);
	for(int i=1; i<=Q; i++){
		int t, a, b; scanf("%d%d%d", &t, &a, &b);
		if(t==1){
			Seg.Update(a, (ll)b);
			C[a] = (ll)b;
		}else if(t==2){
			Seg.Lazy(a, b);
		}else{
			printf("%lld\n", Seg.Sum(a, b));
		}
	}
	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &N, &Q, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &C[i]);
   ~~~~~^~~~~~~~~~~~~~~
sterilizing.cpp:135:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t, a, b; scanf("%d%d%d", &t, &a, &b);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 5 ms 1272 KB Output is correct
4 Correct 12 ms 1128 KB Output is correct
5 Correct 14 ms 2040 KB Output is correct
6 Correct 14 ms 1912 KB Output is correct
7 Correct 14 ms 1912 KB Output is correct
8 Correct 14 ms 1912 KB Output is correct
9 Correct 15 ms 1912 KB Output is correct
10 Correct 19 ms 2040 KB Output is correct
11 Correct 14 ms 1912 KB Output is correct
12 Correct 14 ms 1912 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 27444 KB Output is correct
2 Correct 292 ms 19388 KB Output is correct
3 Correct 314 ms 41592 KB Output is correct
4 Correct 449 ms 53112 KB Output is correct
5 Correct 514 ms 54264 KB Output is correct
6 Correct 646 ms 54312 KB Output is correct
7 Correct 445 ms 54172 KB Output is correct
8 Correct 391 ms 54132 KB Output is correct
9 Correct 310 ms 54028 KB Output is correct
10 Correct 320 ms 54008 KB Output is correct
11 Correct 312 ms 54100 KB Output is correct
12 Correct 302 ms 53980 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 4240 KB Output is correct
2 Correct 126 ms 23380 KB Output is correct
3 Correct 177 ms 23716 KB Output is correct
4 Correct 429 ms 14048 KB Output is correct
5 Correct 665 ms 52672 KB Output is correct
6 Correct 681 ms 52712 KB Output is correct
7 Correct 445 ms 52736 KB Output is correct
8 Correct 637 ms 52712 KB Output is correct
9 Correct 445 ms 52652 KB Output is correct
10 Correct 456 ms 52728 KB Output is correct
11 Correct 466 ms 52780 KB Output is correct
12 Correct 453 ms 52804 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 28252 KB Output is correct
2 Correct 454 ms 29044 KB Output is correct
3 Correct 292 ms 24516 KB Output is correct
4 Correct 473 ms 18752 KB Output is correct
5 Correct 683 ms 54008 KB Output is correct
6 Correct 638 ms 54088 KB Output is correct
7 Correct 751 ms 54136 KB Output is correct
8 Correct 773 ms 54152 KB Output is correct
9 Correct 584 ms 53880 KB Output is correct
10 Correct 468 ms 54004 KB Output is correct
11 Correct 471 ms 53916 KB Output is correct
12 Correct 484 ms 53848 KB Output is correct