oj.uz

Submission #333313

# Submission time Handle Problem Language Result Execution time Memory
333313 2020-12-05T11:24:50 Z GioChkhaidze Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 5868 KB 
#include <bits/stdc++.h>

#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long

using namespace std;

const int N=1e5+5;

int n,q,k;
int a[N];
ll v[4*N];

void Build(Tree) {
	if (l==r) {
		v[h]=a[l];
		return ;
	}
	
	Build(Left);
	Build(Right);
	
	v[h]=v[(h<<1)]+v[((h<<1)|1)];
}

int t,id,vl;
void Up(Tree) {
	if (id<l || r<id) return ;
	if (l==id && r==id) {
		v[h]=a[l];
		return ;
	}
	
	Up(Left);
	Up(Right);
	
	v[h]=v[(h<<1)]+v[((h<<1)|1)];
}

int L,R;
void Upd(Tree) {
	if (R<l || r<L) return ;
	if (l==r) {
		v[h]/=k;
		return ;
	}
	
	Upd(Left);
	Upd(Right);	
	v[h]=v[(h<<1)]+v[((h<<1)|1)];
}

ll Get(Tree) {
	if (R<l || r<L) return 0;
	if (L<=l && r<=R) return v[h];
	return Get(Left)+Get(Right);
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n>>q>>k;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
	}
	
	Build(1,1,n);
	
	for (int i=1; i<=q; i++) {
		cin>>t;
		if (t==1) {
			cin>>id>>vl;
			a[id]=vl;
			Up(1,1,n);
		}
			else
		if (t==2) {
			cin>>L>>R;
			if (k==1) continue;
			Upd(1,1,n);
		}
			else
		if (t==3) {
			cin>>L>>R;
			cout<<Get(1,1,n)<<"\n";
		}
	}
}

Compilation message

sterilizing.cpp:61:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   61 | main () {
      |       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6 ms 492 KB Output is correct
5 Correct 11 ms 492 KB Output is correct
6 Correct 11 ms 492 KB Output is correct
7 Correct 11 ms 492 KB Output is correct
8 Correct 11 ms 492 KB Output is correct
9 Correct 11 ms 492 KB Output is correct
10 Correct 11 ms 492 KB Output is correct
11 Correct 11 ms 492 KB Output is correct
12 Correct 12 ms 492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 3948 KB Output is correct
2 Correct 62 ms 3564 KB Output is correct
3 Correct 45 ms 4716 KB Output is correct
4 Correct 57 ms 5356 KB Output is correct
5 Correct 74 ms 5868 KB Output is correct
6 Correct 71 ms 5740 KB Output is correct
7 Correct 74 ms 5740 KB Output is correct
8 Correct 78 ms 5740 KB Output is correct
9 Correct 77 ms 5676 KB Output is correct
10 Correct 69 ms 5740 KB Output is correct
11 Correct 65 ms 5612 KB Output is correct
12 Correct 67 ms 5612 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 1004 KB Output is correct
2 Correct 648 ms 2076 KB Output is correct
3 Correct 1018 ms 2120 KB Output is correct
4 Correct 2317 ms 2444 KB Output is correct
5 Execution timed out 5057 ms 3996 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3430 ms 3428 KB Output is correct
2 Correct 4011 ms 3808 KB Output is correct
3 Correct 2096 ms 3052 KB Output is correct
4 Correct 2889 ms 3172 KB Output is correct
5 Execution timed out 5096 ms 4892 KB Time limit exceeded
6 Halted 0 ms 0 KB -