oj.uz

Submission #960309

# Submission time Handle Problem Language Result Execution time Memory
960309 2024-04-10T08:34:25 Z pcc Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 156 ms 9860 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const ll mxn = 1e5+10;
int arr[mxn];

struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
	pll seg[mxn*4];
	void build(int now,int l,int r){
		if(l == r){
			seg[now].fs = seg[now].sc = arr[l];
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		seg[now].fs = seg[ls].fs+seg[rs].fs;
		seg[now].sc = max(seg[ls].sc,seg[rs].sc);
	}
	void chval(int now,int l,int r,int p,int v){
		if(l == r){
			seg[now].fs = seg[now].sc = v;
			return;
		}
		if(mid>=p)chval(ls,l,mid,p,v);
		else chval(rs,mid+1,r,p,v);
		seg[now].fs = seg[ls].fs+seg[rs].fs;
		seg[now].sc = max(seg[ls].sc,seg[rs].sc);
	}
	void modify(int now,int l,int r,int s,int e,int k){
		if(k == 1)return;
		if(!seg[now].sc)return;
		if(l == r){
			seg[now].fs = seg[now].sc = seg[now].fs/k;
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,k);
		if(mid<e)modify(rs,mid+1,r,s,e,k);
		seg[now].fs = seg[ls].fs+seg[rs].fs;
		seg[now].sc = max(seg[ls].sc,seg[rs].sc);
	}
	ll getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now].fs;
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return getval(ls,l,mid,s,e)+getval(rs,mid+1,r,s,e);
	}
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
};

SEG seg;
int N,Q,K;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q>>K;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	seg.build(0,1,N);
	while(Q--){
		int t,a,b;
		cin>>t>>a>>b;
		if(t == 1)seg.chval(0,1,N,a,b);
		else if(t == 2)seg.modify(0,1,N,a,b,K);
		else cout<<seg.getval(0,1,N,a,b)<<'\n';
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 2 ms 2464 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 3 ms 2716 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 4 ms 2532 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7132 KB Output is correct
2 Correct 30 ms 6736 KB Output is correct
3 Correct 26 ms 8948 KB Output is correct
4 Correct 33 ms 9556 KB Output is correct
5 Correct 41 ms 9860 KB Output is correct
6 Correct 40 ms 9808 KB Output is correct
7 Correct 41 ms 9812 KB Output is correct
8 Correct 41 ms 9820 KB Output is correct
9 Correct 38 ms 9812 KB Output is correct
10 Correct 42 ms 9732 KB Output is correct
11 Correct 37 ms 9808 KB Output is correct
12 Correct 44 ms 9812 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5208 KB Output is correct
2 Correct 8 ms 4956 KB Output is correct
3 Correct 12 ms 5212 KB Output is correct
4 Correct 32 ms 5976 KB Output is correct
5 Correct 41 ms 8540 KB Output is correct
6 Correct 41 ms 8552 KB Output is correct
7 Correct 36 ms 8696 KB Output is correct
8 Correct 39 ms 8536 KB Output is correct
9 Correct 37 ms 8436 KB Output is correct
10 Correct 41 ms 8284 KB Output is correct
11 Correct 36 ms 8392 KB Output is correct
12 Correct 36 ms 8284 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6484 KB Output is correct
2 Correct 61 ms 6544 KB Output is correct
3 Correct 70 ms 5968 KB Output is correct
4 Correct 75 ms 6740 KB Output is correct
5 Correct 87 ms 9756 KB Output is correct
6 Correct 94 ms 9792 KB Output is correct
7 Correct 81 ms 9800 KB Output is correct
8 Correct 113 ms 9808 KB Output is correct
9 Correct 103 ms 9556 KB Output is correct
10 Correct 116 ms 9520 KB Output is correct
11 Correct 93 ms 9472 KB Output is correct
12 Correct 156 ms 9608 KB Output is correct