oj.uz

Submission #526810

# Submission time Handle Problem Language Result Execution time Memory
526810 2022-02-16T07:44:42 Z ac2hu Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 11440 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){
		if(t[v].mx == t[v].sum && t[v].sum == 0){
            return;
        }
        else{
            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 7 ms 9680 KB Output is correct
2 Correct 6 ms 9724 KB Output is correct
3 Correct 5 ms 9716 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 7 ms 9760 KB Output is correct
6 Correct 7 ms 9804 KB Output is correct
7 Correct 7 ms 9804 KB Output is correct
8 Correct 8 ms 9804 KB Output is correct
9 Correct 8 ms 9728 KB Output is correct
10 Correct 7 ms 9804 KB Output is correct
11 Correct 7 ms 9792 KB Output is correct
12 Correct 8 ms 9736 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 10180 KB Output is correct
2 Correct 15 ms 10316 KB Output is correct
3 Correct 20 ms 10432 KB Output is correct
4 Correct 53 ms 10800 KB Output is correct
5 Correct 82 ms 11372 KB Output is correct
6 Correct 69 ms 11364 KB Output is correct
7 Execution timed out 5094 ms 11440 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 10948 KB Output is correct
2 Correct 100 ms 10764 KB Output is correct
3 Correct 121 ms 10708 KB Output is correct
4 Correct 134 ms 10680 KB Output is correct
5 Correct 146 ms 11240 KB Output is correct
6 Correct 167 ms 11240 KB Output is correct
7 Correct 135 ms 11240 KB Output is correct
8 Correct 197 ms 11116 KB Output is correct
9 Correct 178 ms 10820 KB Output is correct
10 Correct 208 ms 10728 KB Output is correct
11 Correct 165 ms 10836 KB Output is correct
12 Correct 298 ms 10712 KB Output is correct