oj.uz

답안 #526811

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526811 2022-02-16T07:47:50 Z ac2hu Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 10820 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--;
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9732 KB Output is correct
4 Correct 8 ms 9676 KB Output is correct
5 Correct 8 ms 9736 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 7 ms 9736 KB Output is correct
10 Correct 7 ms 9676 KB Output is correct
11 Correct 7 ms 9676 KB Output is correct
12 Correct 7 ms 9676 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5059 ms 10396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 9676 KB Output is correct
2 Correct 13 ms 10060 KB Output is correct
3 Correct 17 ms 9988 KB Output is correct
4 Correct 45 ms 10064 KB Output is correct
5 Correct 56 ms 10512 KB Output is correct
6 Correct 52 ms 10536 KB Output is correct
7 Execution timed out 5081 ms 10616 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 10268 KB Output is correct
2 Correct 100 ms 10260 KB Output is correct
3 Correct 122 ms 10180 KB Output is correct
4 Correct 116 ms 10180 KB Output is correct
5 Correct 119 ms 10728 KB Output is correct
6 Correct 142 ms 10732 KB Output is correct
7 Correct 171 ms 10712 KB Output is correct
8 Correct 182 ms 10744 KB Output is correct
9 Correct 169 ms 10788 KB Output is correct
10 Correct 210 ms 10820 KB Output is correct
11 Correct 144 ms 10788 KB Output is correct
12 Correct 261 ms 10696 KB Output is correct