oj.uz

Submission #526808

# Submission time Handle Problem Language Result Execution time Memory
526808 2022-02-16T07:43:30 Z ac2hu Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 11564 KB 
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
const int N = 1e5 + 10;
int n,q,k;
int a[N];
struct node{
	int mx, sum;
	bool checked = false;
} t[4*N];
node nulln = {0,0,false};
node merge(node a, node b){
	node ans;
	ans.mx = max(a.mx,b.mx);
	ans.sum = a.sum + b.sum;
    ans.checked = false;
	return ans;
}
void push(int v,int tl,int tr){
    // deb(v,tl,tr);
	if(!t[v].checked)return;
	t[v].checked = false;
	if(tl != tr){
		t[v*2] = t[v*2 + 1] = {0,0,true};
	}
}
void propagate(int v,int l,int r){
	if(t[v].mx < k){
		t[v] = {0,0,true};
	}
	else if(l == r){
		t[v].mx /= k;
		t[v].sum /= k;
	}
	else{
        push(v,l,r);
		int tm = (l + r)/2;
		propagate(v*2,l,tm);
		propagate(v*2 + 1,tm + 1,r);
		t[v] = merge(t[v*2],t[v*2 + 1]);
	}
}
void build(int v,int tl,int tr){
	if(tl == tr)
		t[v] = {a[tl],a[tl]};
	else{
        // push(v,tl,tr);
		int tm = (tl + tr)/2;
		build(v*2,tl,tm);
		build(v*2 + 1,tm + 1,tr);
		t[v] = merge(t[v*2],t[v*2  + 1]);
	}
}
int query(int l,int r,int v, int tl,int tr){
    // deb(l,r,v,tl,tr);
	if(l > r)
		return 0;
	else if(l == tl && r == tr){
		return t[v].sum;
    }
	else{
        // assert(tl != tr);
		int tm = (tl + tr)/2;
        push(v,tl,tr);
		return query(l,min(r,tm),v*2,tl,tm) + query(max(l,tm + 1),r,v*2 + 1,tm + 1,tr);
	}
}
void update1(int idx,int val, int v,int tl,int tr){
	if(tl == tr)
		t[v] = {val,val};
	else{
        push(v,tl,tr);
		int tm = (tl + tr)/2;
		if(idx <= tm)
			update1(idx,val,v*2,tl,tm);
		else
			update1(idx,val,v*2 + 1,tm + 1,tr);
		t[v] = merge(t[v*2],t[v*2 + 1]);
    }
}
void update2(int l,int r,int v,int tl,int tr){
	if(l > r)
		return;
	else if(l == tl && r == tr){
		propagate(v,tl,tr);
	}
	else{
        if(t[v].checked){
            push(v,tl,tr);
            return;
        }
		int tm = (tl + tr)/2;
		update2(l,min(r,tm),v*2,tl,tm);
		update2(max(l,tm + 1),r,v*2 + 1,tm + 1,tr);
		t[v] = merge(t[v*2], t[v*2 + 1]);
	}
}
signed main() {
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin >> n >> q >> k;
	for(int i = 0;i<n;i++)cin >> a[i];
	build(1,0,n-1);
    while(q--){
        // break;
        int t;cin >> t;
        if(t == 1){
            int a,b;cin >> a >> b;
            a--;
            update1(a,b,1,0,n-1);
        }
        else if(t == 2){
            int l,r;cin >> l >> r;
            l--;r--;
            update2(l, r, 1,0,n-1);
        }
        else{
            int l,r;cin >> l >> r;
            l--;r--;
            cout << query(l,r,1,0,n-1) << "\n";
            // break;
        }
        // for(int i = 0;i<n;i++)
        //     cout << query(i,i,1,0,n-1) << " ";
        // cout << "\n";
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5054 ms 10500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 9676 KB Output is correct
2 Correct 18 ms 9980 KB Output is correct
3 Correct 19 ms 10084 KB Output is correct
4 Correct 51 ms 9944 KB Output is correct
5 Correct 62 ms 10496 KB Output is correct
6 Correct 71 ms 10608 KB Output is correct
7 Execution timed out 5077 ms 10544 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10264 KB Output is correct
2 Correct 110 ms 10244 KB Output is correct
3 Correct 134 ms 10180 KB Output is correct
4 Correct 125 ms 10180 KB Output is correct
5 Correct 149 ms 10680 KB Output is correct
6 Correct 168 ms 10756 KB Output is correct
7 Correct 143 ms 10724 KB Output is correct
8 Correct 214 ms 11248 KB Output is correct
9 Correct 183 ms 11380 KB Output is correct
10 Correct 266 ms 11468 KB Output is correct
11 Correct 159 ms 11440 KB Output is correct
12 Correct 299 ms 11564 KB Output is correct