oj.uz

Submission #187551

# Submission time Handle Problem Language Result Execution time Memory
187551 2020-01-13T03:27:28 Z dndhk Sterilizing Spray (JOI15_sterilizing) C++14
20 / 100
 653 ms 54284 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[30];
		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){
			for(int i=0; i<MAX_K-1; i++){
				seg[idx].d[i] = seg[idx].d[i+1];
			}
			seg[idx].d[MAX_K-1] = seg[idx].d[MAX_K-2]/K;
			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 0;
		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, b);
			C[a] = 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:128: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:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &C[i]);
   ~~~~~^~~~~~~~~~~~~~~
sterilizing.cpp:134: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 4 ms 764 KB Output is correct
3 Correct 6 ms 1272 KB Output is correct
4 Incorrect 11 ms 1144 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 315 ms 27736 KB Output is correct
2 Correct 260 ms 19492 KB Output is correct
3 Correct 275 ms 41688 KB Output is correct
4 Correct 358 ms 53064 KB Output is correct
5 Correct 419 ms 54204 KB Output is correct
6 Correct 415 ms 54136 KB Output is correct
7 Correct 425 ms 54188 KB Output is correct
8 Correct 421 ms 54284 KB Output is correct
9 Correct 342 ms 54060 KB Output is correct
10 Correct 349 ms 54000 KB Output is correct
11 Correct 351 ms 54076 KB Output is correct
12 Correct 423 ms 54136 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4260 KB Output is correct
2 Correct 121 ms 23412 KB Output is correct
3 Correct 166 ms 23672 KB Output is correct
4 Correct 424 ms 14200 KB Output is correct
5 Correct 652 ms 53008 KB Output is correct
6 Correct 645 ms 52984 KB Output is correct
7 Correct 397 ms 52788 KB Output is correct
8 Correct 653 ms 52856 KB Output is correct
9 Correct 451 ms 52728 KB Output is correct
10 Correct 468 ms 52600 KB Output is correct
11 Correct 447 ms 52660 KB Output is correct
12 Correct 456 ms 52728 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 28264 KB Output is correct
2 Correct 453 ms 28724 KB Output is correct
3 Incorrect 291 ms 24600 KB Output isn't correct
4 Halted 0 ms 0 KB -