oj.uz

Submission #526807

# Submission time Handle Problem Language Result Execution time Memory
526807 2022-02-16T07:41:36 Z ac2hu Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 13204 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{
        push(v,tl,tr);
		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 9728 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 5 ms 9728 KB Output is correct
4 Correct 8 ms 9724 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Correct 8 ms 9784 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 7 ms 9724 KB Output is correct
9 Correct 10 ms 9780 KB Output is correct
10 Correct 8 ms 9792 KB Output is correct
11 Correct 7 ms 9804 KB Output is correct
12 Correct 8 ms 9732 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10132 KB Output is correct
2 Correct 17 ms 10304 KB Output is correct
3 Correct 25 ms 10424 KB Output is correct
4 Correct 67 ms 10304 KB Output is correct
5 Correct 79 ms 10880 KB Output is correct
6 Correct 90 ms 10884 KB Output is correct
7 Execution timed out 5061 ms 10892 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 10544 KB Output is correct
2 Correct 103 ms 11972 KB Output is correct
3 Correct 138 ms 11256 KB Output is correct
4 Correct 142 ms 11940 KB Output is correct
5 Correct 153 ms 13204 KB Output is correct
6 Correct 214 ms 13204 KB Output is correct
7 Correct 155 ms 13156 KB Output is correct
8 Correct 232 ms 13116 KB Output is correct
9 Correct 197 ms 13080 KB Output is correct
10 Correct 269 ms 13020 KB Output is correct
11 Correct 216 ms 13136 KB Output is correct
12 Correct 390 ms 13044 KB Output is correct