oj.uz

Submission #526802

# Submission time Handle Problem Language Result Execution time Memory
526802 2022-02-16T07:35:57 Z ac2hu Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 7004 KB 
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
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;
	return ans;
}
void push(int v,int tl,int tr){
	if(t[v].checked == false)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{
		int tm = (l + r)/2;
        push(v,l,r);
		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){
    // 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--){
        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;
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5444 KB Output is correct
2 Correct 14 ms 5452 KB Output is correct
3 Correct 20 ms 5552 KB Output is correct
4 Correct 58 ms 6360 KB Output is correct
5 Correct 67 ms 6820 KB Output is correct
6 Correct 69 ms 6788 KB Output is correct
7 Execution timed out 5061 ms 6344 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 6824 KB Output isn't correct
2 Halted 0 ms 0 KB -