oj.uz

Submission #113615

# Submission time Handle Problem Language Result Execution time Memory
113615 2019-05-27T06:22:17 Z Diuven Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 725 ms 10488 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;

const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;

int n, q, k, A[MAX];
set<int> S;

class Seg_t{
	lint T[1<<18];
	void upt(int v, int s, int e, int p, int x){
		if(p<s || e<p) return;
		if(s==e){ T[v]=x; return; }
		upt(v*2,s,(s+e)/2,p,x); upt(v*2+1,(s+e)/2+1,e,p,x);
		T[v]=T[v*2]+T[v*2+1];
	}
	lint sum(int v, int s, int e, int l, int r){
		if(e<l || r<s) return 0;
		if(l<=s && e<=r) return T[v];
		return sum(v*2,s,(s+e)/2,l,r) + sum(v*2+1,(s+e)/2+1,e,l,r);
	}
  public:
    void upt(int p, int x){ upt(1,1,n,p,x); }
	lint sum(int l, int r){ return sum(1,1,n,l,r); }
} Seg;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n>>q>>k;
	for(int i=1; i<=n; i++){
		cin>>A[i]; Seg.upt(i, A[i]);
		if(A[i]!=0) S.insert(i);
	}

	for(int i=1; i<=q; i++){
		int o,x,y; cin>>o>>x>>y;
		if(o==1){
			A[x]=y, Seg.upt(x, A[x]);
			if(A[x]!=0) S.insert(x);
		}
		else if(o==2){
			if(k==1) continue;
			auto lit=S.lower_bound(x), rit=S.upper_bound(y);
			vector<int> V;
			while(lit!=rit){
				int p=*lit; lit++;
				A[p]/=k, Seg.upt(p, A[p]);
				if(A[p]==0) V.push_back(p);
			}
			for(int p:V) S.erase(p);
		}
		else if(o==3){
			cout<<Seg.sum(x,y)<<'\n';
		}
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 11 ms 512 KB Output is correct
5 Correct 12 ms 640 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 11 ms 640 KB Output is correct
8 Correct 11 ms 640 KB Output is correct
9 Correct 14 ms 640 KB Output is correct
10 Correct 11 ms 640 KB Output is correct
11 Correct 10 ms 640 KB Output is correct
12 Correct 11 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6264 KB Output is correct
2 Correct 74 ms 5108 KB Output is correct
3 Correct 87 ms 8312 KB Output is correct
4 Correct 129 ms 9916 KB Output is correct
5 Correct 136 ms 10360 KB Output is correct
6 Correct 136 ms 10404 KB Output is correct
7 Correct 141 ms 10488 KB Output is correct
8 Correct 139 ms 10472 KB Output is correct
9 Correct 133 ms 10392 KB Output is correct
10 Correct 132 ms 10360 KB Output is correct
11 Correct 132 ms 10360 KB Output is correct
12 Correct 133 ms 10360 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1152 KB Output is correct
2 Correct 29 ms 2944 KB Output is correct
3 Correct 36 ms 3168 KB Output is correct
4 Correct 64 ms 2816 KB Output is correct
5 Correct 115 ms 6776 KB Output is correct
6 Correct 111 ms 6776 KB Output is correct
7 Correct 112 ms 7160 KB Output is correct
8 Correct 110 ms 6776 KB Output is correct
9 Correct 98 ms 6692 KB Output is correct
10 Correct 98 ms 6692 KB Output is correct
11 Correct 97 ms 6564 KB Output is correct
12 Correct 100 ms 6648 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 5848 KB Output is correct
2 Correct 203 ms 5988 KB Output is correct
3 Correct 340 ms 5112 KB Output is correct
4 Correct 211 ms 4648 KB Output is correct
5 Correct 336 ms 10384 KB Output is correct
6 Correct 392 ms 10360 KB Output is correct
7 Correct 325 ms 10232 KB Output is correct
8 Correct 525 ms 10488 KB Output is correct
9 Correct 436 ms 10224 KB Output is correct
10 Correct 523 ms 10276 KB Output is correct
11 Correct 353 ms 10340 KB Output is correct
12 Correct 725 ms 10296 KB Output is correct