Submission #187597

#	Time	Username	Problem	Language	Result	Execution time	Memory
187597		dndhk	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	773 ms	54312 KiB

sterilizing

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75