Submission #40907

#	Time	Username	Problem	Language	Result	Execution time	Memory
40907		wzy	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	365 ms	5292 KiB

sterilizing

#include <stdio.h>
#include <stdint.h>
#include <vector>
#define int long long
#define ll int
using namespace std;
int n , q, k ;
struct node{
	ll sum = 0;
	ll rmq = 0;	
}st[1000000];



void build(int l = 0 , int r = n -1 , int curr = 1){
	int mid = (l+r)/2;
	if(l == r){
		scanf("%lld" , &st[curr].sum);
		st[curr].rmq = st[curr].sum;
		return;
	}
	build(l , mid , 2*curr);
	build(mid + 1 , r , 2*curr + 1);
	st[curr].sum = st[2*curr].sum + st[2*curr + 1].sum;
	st[curr].rmq = max(st[2*curr].rmq , st[2*curr + 1].rmq);
}


void set_value(int x , int v , int l = 0 , int r = n - 1 , int curr = 1){
	int mid = (l+r)/2;
	if(l == x && l == r){
		st[curr].sum = v;
		st[curr].rmq = v;
		return;
	}
	if(x <= mid){
		set_value(x , v , l , mid , 2*curr);
	}
	else set_value(x , v , mid + 1 ,r , 2*curr + 1);
	st[curr].sum = st[2*curr].sum + st[2*curr + 1].sum;
	st[curr].rmq = max(st[2*curr].rmq , st[2*curr + 1].rmq);
}

void set_range(int x , int y , int l = 0 , int r = n -1 , int curr = 1){
	int mid = (l+r)/2;
	if(l == r){
		st[curr].rmq /= k;
		st[curr].sum /= k;
		return;
	}
	if(l == x && r == y){
		if(st[2*curr].rmq > 0) set_range(l , mid , l , mid , 2*curr);
		if(st[2*curr + 1].rmq > 0) set_range(mid + 1 , r , mid + 1 , r , 2*curr +1);
	}
	else{
		if(y <= mid) set_range(x , y , l , mid , 2*curr);
		else if(x > mid) set_range(x , y , mid + 1 , r , 2*curr + 1);
		else{
			set_range(x , mid , l , mid , 2*curr);
			set_range(mid + 1 , y , mid + 1 , r , 2*curr + 1);
		}
	}
	st[curr].sum = st[2*curr].sum + st[2*curr + 1].sum;
	st[curr].rmq = max(st[2*curr].rmq , st[2*curr + 1].rmq);
}

ll sum_range(int x , int y ,int l = 0 , int r = n-1  ,int curr = 1){
	int mid = (l+r)/2;
	if(l == x && r == y){
		return st[curr].sum;
	}
	if(y <= mid) return sum_range(x,y,l,mid,2*curr);
	if(x > mid) return sum_range(x,y,mid+1,r,2*curr + 1);
	return (sum_range(x , mid , l , mid , 2*curr) + sum_range(mid + 1 , y , mid + 1 , r ,2*curr + 1));
}




int32_t main(){
	scanf("%lld%lld%lld" , &n , &q , &k);
	build();
	while(q--){
		int x,y,z;
		scanf("%lld%lld%lld" , &x,  &y , &z);
		if(x == 1){
			set_value(y  - 1, z);
		}
		else if(x == 2){
			if(k != 1){
				set_range(y - 1 , z - 1);
			}
		}
		else{
			ll w = sum_range(y - 1 , z-1);
			printf("%lld\n" , w);
		}
	}
}

Compilation message (stderr)

sterilizing.cpp: In function 'void build(long long int, long long int, long long int)':
sterilizing.cpp:18:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld" , &st[curr].sum);
                                ^
sterilizing.cpp: In function 'int32_t main()':
sterilizing.cpp:81:38: 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:85:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld" , &x,  &y , &z);
                                       ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75