oj.uz

Submission #526812

# Submission time Handle Problem Language Result Execution time Memory
526812 2022-02-16T07:50:59 Z ac2hu Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 277 ms 13444 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];
inline 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;
}
inline 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{
		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{
		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){
	if(l > r)
		return 0;
	else if(l == tl && r == tr){
		return t[v].sum;
    }
	else{
        if(t[v].checked){
            push(v,tl,tr);
            return 0;
        }
		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--;
	        if(k > 1){
	            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 4 ms 9676 KB Output is correct
3 Correct 5 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 9736 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct
8 Correct 7 ms 9676 KB Output is correct
9 Correct 9 ms 9744 KB Output is correct
10 Correct 9 ms 9676 KB Output is correct
11 Correct 8 ms 9676 KB Output is correct
12 Correct 7 ms 9732 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 10900 KB Output is correct
2 Correct 40 ms 11972 KB Output is correct
3 Correct 48 ms 12204 KB Output is correct
4 Correct 47 ms 12848 KB Output is correct
5 Correct 62 ms 13444 KB Output is correct
6 Correct 60 ms 13292 KB Output is correct
7 Correct 64 ms 13380 KB Output is correct
8 Correct 66 ms 13404 KB Output is correct
9 Correct 53 ms 13184 KB Output is correct
10 Correct 56 ms 13256 KB Output is correct
11 Correct 68 ms 13276 KB Output is correct
12 Correct 60 ms 13208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 9680 KB Output is correct
2 Correct 12 ms 10064 KB Output is correct
3 Correct 17 ms 10080 KB Output is correct
4 Correct 56 ms 10056 KB Output is correct
5 Correct 66 ms 10504 KB Output is correct
6 Correct 64 ms 10520 KB Output is correct
7 Correct 54 ms 11016 KB Output is correct
8 Correct 51 ms 11912 KB Output is correct
9 Correct 66 ms 11716 KB Output is correct
10 Correct 81 ms 11764 KB Output is correct
11 Correct 63 ms 11716 KB Output is correct
12 Correct 67 ms 11844 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10256 KB Output is correct
2 Correct 87 ms 10244 KB Output is correct
3 Correct 116 ms 10108 KB Output is correct
4 Correct 118 ms 10160 KB Output is correct
5 Correct 134 ms 10744 KB Output is correct
6 Correct 143 ms 10736 KB Output is correct
7 Correct 122 ms 10740 KB Output is correct
8 Correct 191 ms 10732 KB Output is correct
9 Correct 177 ms 10824 KB Output is correct
10 Correct 205 ms 10728 KB Output is correct
11 Correct 150 ms 10788 KB Output is correct
12 Correct 277 ms 10736 KB Output is correct