oj.uz

Submission #68371

# Submission time Handle Problem Language Result Execution time Memory
68371 2018-08-16T21:17:02 Z Kerim Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 443 ms 30128 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
ll sum[MAXN<<2];
int mx[MAXN<<2],arr[MAXN],k;
void build(int nd,int x,int y){
	if(x==y){
		sum[nd]=mx[nd]=arr[x];
		return;
	}
	int mid=(x+y)>>1;
	build(nd<<1,x,mid);
	build(nd<<1|1,mid+1,y);
	sum[nd]=sum[nd<<1]+sum[nd<<1|1];
	mx[nd]=max(mx[nd<<1],mx[nd<<1|1]);
}
void upd(int p,int v,int nd,int x,int y){
	if(x==y){
		sum[nd]=mx[nd]=v;
		return;
	}
	int mid=(x+y)>>1;
	if(p<=mid)
		upd(p,v,nd<<1,x,mid);
	else	
		upd(p,v,nd<<1|1,mid+1,y);
	sum[nd]=sum[nd<<1]+sum[nd<<1|1];
	mx[nd]=max(mx[nd<<1],mx[nd<<1|1]);
}
void inc(int l,int r,int nd,int x,int y){
	if(l>y or x>r or !mx[nd])
		return;
	if(x==y){
		sum[nd]/=k;
		mx[nd]/=k;
		return;
	}	
	int mid=(x+y)>>1;
	inc(l,r,nd<<1,x,mid);
	inc(l,r,nd<<1|1,mid+1,y);
	sum[nd]=sum[nd<<1]+sum[nd<<1|1];
	mx[nd]=max(mx[nd<<1],mx[nd<<1|1]);
}
ll tap(int l,int r,int nd,int x,int y){
	if(l>y or x>r)
		return 0;
	if(l<=x and y<=r)
		return sum[nd];
	int mid=(x+y)>>1;
	return tap(l,r,nd<<1,x,mid)+tap(l,r,nd<<1|1,mid+1,y);	
}
int main(){
    //~ freopen("file.in", "r", stdin);
    int n,q;
    scanf("%d%d%d",&n,&q,&k);
    for(int i=1;i<=n;i++)
		scanf("%d",arr+i);
	build(1,1,n);
	while(q--){
		int t,l,r;
		scanf("%d%d%d",&t,&l,&r);
		if(t==1)
			upd(l,r,1,1,n);
		else if(t==2){
			if(k!=1)
				inc(l,r,1,1,n);
		}
		else
			printf("%lld\n",tap(l,r,1,1,n));
	}	
	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&q,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",arr+i);
   ~~~~~^~~~~~~~~~~~
sterilizing.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&t,&l,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 8 ms 560 KB Output is correct
5 Correct 7 ms 560 KB Output is correct
6 Correct 7 ms 560 KB Output is correct
7 Correct 6 ms 628 KB Output is correct
8 Correct 7 ms 628 KB Output is correct
9 Correct 10 ms 628 KB Output is correct
10 Correct 6 ms 628 KB Output is correct
11 Correct 7 ms 628 KB Output is correct
12 Correct 7 ms 628 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 3384 KB Output is correct
2 Correct 71 ms 4924 KB Output is correct
3 Correct 64 ms 8092 KB Output is correct
4 Correct 85 ms 10424 KB Output is correct
5 Correct 104 ms 12988 KB Output is correct
6 Correct 95 ms 15436 KB Output is correct
7 Correct 98 ms 18012 KB Output is correct
8 Correct 92 ms 20448 KB Output is correct
9 Correct 81 ms 22788 KB Output is correct
10 Correct 89 ms 25120 KB Output is correct
11 Correct 82 ms 27400 KB Output is correct
12 Correct 97 ms 29576 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29576 KB Output is correct
2 Correct 18 ms 29576 KB Output is correct
3 Correct 24 ms 29576 KB Output is correct
4 Correct 110 ms 29576 KB Output is correct
5 Correct 93 ms 29576 KB Output is correct
6 Correct 91 ms 29576 KB Output is correct
7 Correct 83 ms 29748 KB Output is correct
8 Correct 81 ms 29748 KB Output is correct
9 Correct 77 ms 29748 KB Output is correct
10 Correct 84 ms 29748 KB Output is correct
11 Correct 80 ms 29832 KB Output is correct
12 Correct 74 ms 29832 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 29832 KB Output is correct
2 Correct 135 ms 29832 KB Output is correct
3 Correct 149 ms 29832 KB Output is correct
4 Correct 162 ms 29832 KB Output is correct
5 Correct 181 ms 29920 KB Output is correct
6 Correct 283 ms 30076 KB Output is correct
7 Correct 170 ms 30076 KB Output is correct
8 Correct 265 ms 30076 KB Output is correct
9 Correct 228 ms 30128 KB Output is correct
10 Correct 260 ms 30128 KB Output is correct
11 Correct 202 ms 30128 KB Output is correct
12 Correct 443 ms 30128 KB Output is correct