oj.uz

Submission #40907

# Submission time Handle Problem Language Result Execution time Memory
40907 2018-02-09T22:56:54 Z wzy Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 365 ms 5292 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 252 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 5 ms 728 KB Output is correct
7 Correct 7 ms 728 KB Output is correct
8 Correct 7 ms 728 KB Output is correct
9 Correct 7 ms 728 KB Output is correct
10 Correct 6 ms 728 KB Output is correct
11 Correct 6 ms 728 KB Output is correct
12 Correct 6 ms 728 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2988 KB Output is correct
2 Correct 60 ms 3000 KB Output is correct
3 Correct 64 ms 4988 KB Output is correct
4 Correct 83 ms 5240 KB Output is correct
5 Correct 94 ms 5240 KB Output is correct
6 Correct 90 ms 5240 KB Output is correct
7 Correct 89 ms 5240 KB Output is correct
8 Correct 84 ms 5240 KB Output is correct
9 Correct 75 ms 5240 KB Output is correct
10 Correct 75 ms 5240 KB Output is correct
11 Correct 77 ms 5240 KB Output is correct
12 Correct 79 ms 5240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5240 KB Output is correct
2 Correct 19 ms 5240 KB Output is correct
3 Correct 25 ms 5240 KB Output is correct
4 Correct 69 ms 5240 KB Output is correct
5 Correct 95 ms 5240 KB Output is correct
6 Correct 92 ms 5240 KB Output is correct
7 Correct 67 ms 5240 KB Output is correct
8 Correct 90 ms 5240 KB Output is correct
9 Correct 91 ms 5240 KB Output is correct
10 Correct 90 ms 5240 KB Output is correct
11 Correct 98 ms 5240 KB Output is correct
12 Correct 91 ms 5240 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 5240 KB Output is correct
2 Correct 123 ms 5240 KB Output is correct
3 Correct 151 ms 5240 KB Output is correct
4 Correct 149 ms 5240 KB Output is correct
5 Correct 193 ms 5264 KB Output is correct
6 Correct 224 ms 5264 KB Output is correct
7 Correct 184 ms 5264 KB Output is correct
8 Correct 281 ms 5264 KB Output is correct
9 Correct 221 ms 5264 KB Output is correct
10 Correct 263 ms 5264 KB Output is correct
11 Correct 249 ms 5272 KB Output is correct
12 Correct 365 ms 5292 KB Output is correct