oj.uz

Submission #288907

# Submission time Handle Problem Language Result Execution time Memory
288907 2020-09-02T06:52:32 Z YJU Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 507 ms 75128 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=1e6+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll n,m,k,x,y,seg[4*N][35],tag[4*N],p[35],ty,C;

void push(ll id){
	if(k==1)return;
	if(tag[id]){
		tag[id*2]+=tag[id];tag[id*2+1]+=tag[id];
		REP(i,C)seg[id*2][i]=seg[id*2][min(33LL,i+tag[id])],seg[id*2+1][i]=seg[id*2+1][min(33LL,i+tag[id])];
		tag[id]=0;
	}
}

void ins(ll id,ll l,ll r,ll to,ll d){
	if(l==r-1){REP(i,C)seg[id][i]=d/p[i];return;}
	ll mid=(l+r)/2;
	push(id);
	if(to<mid){
		ins(id*2,l,mid,to,d);
	}else{
		ins(id*2+1,mid,r,to,d);
	}
	REP(i,C)seg[id][i]=seg[id*2][i]+seg[id*2+1][i];
}

void mod(ll id,ll l,ll r,ll ql,ll qr){
	if(l>=qr||r<=ql)return;
	if(l>=ql&&r<=qr){
		if(k==1)return;
		++tag[id];
		REP(i,C)seg[id][i]=seg[id][i+1];
		return;
	}
	push(id);
	ll mid=(l+r)/2;
	mod(id*2,l,mid,ql,qr);mod(id*2+1,mid,r,ql,qr);
	REP(i,C)seg[id][i]=seg[id*2][i]+seg[id*2+1][i];
}

ll q(ll id,ll l,ll r,ll ql,ll qr){
	if(l>=qr||r<=ql)return 0;
	if(l>=ql&&r<=qr)return seg[id][0];
	push(id);
	ll mid=(l+r)/2;
	return q(id*2,l,mid,ql,qr)+q(id*2+1,mid,r,ql,qr);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>k;
	p[0]=1;
	for(C=1;;C++){
		p[C]=p[C-1]*k;
		if(p[C]>1e9||C>=32)break;
	}
	REP1(i,n)cin>>x,ins(1,1,n+1,i,x);
	while(m--){
		cin>>ty;
		if(ty==1){
			cin>>x>>y;
			ins(1,1,n+1,x,y);
		}else if(ty==2){
			cin>>x>>y;
			mod(1,1,n+1,x,y+1);
		}else{
			cin>>x>>y;
			cout<<q(1,1,n+1,x,y+1)<<"\n";
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 896 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 6 ms 1536 KB Output is correct
5 Correct 7 ms 2720 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 7 ms 2688 KB Output is correct
8 Correct 8 ms 2688 KB Output is correct
9 Correct 7 ms 2688 KB Output is correct
10 Correct 6 ms 2688 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 6 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 36728 KB Output is correct
2 Correct 203 ms 22264 KB Output is correct
3 Correct 249 ms 74104 KB Output is correct
4 Correct 352 ms 74916 KB Output is correct
5 Correct 360 ms 75124 KB Output is correct
6 Correct 379 ms 75048 KB Output is correct
7 Correct 370 ms 75128 KB Output is correct
8 Correct 381 ms 75128 KB Output is correct
9 Correct 327 ms 74988 KB Output is correct
10 Correct 324 ms 75000 KB Output is correct
11 Correct 316 ms 75000 KB Output is correct
12 Correct 316 ms 75000 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4992 KB Output is correct
2 Correct 88 ms 37240 KB Output is correct
3 Correct 94 ms 37240 KB Output is correct
4 Correct 188 ms 18936 KB Output is correct
5 Correct 378 ms 74232 KB Output is correct
6 Correct 507 ms 74232 KB Output is correct
7 Correct 334 ms 72316 KB Output is correct
8 Correct 351 ms 74276 KB Output is correct
9 Correct 227 ms 74232 KB Output is correct
10 Correct 239 ms 74232 KB Output is correct
11 Correct 226 ms 74232 KB Output is correct
12 Correct 257 ms 74488 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 37496 KB Output is correct
2 Correct 212 ms 37496 KB Output is correct
3 Correct 222 ms 37496 KB Output is correct
4 Correct 220 ms 19064 KB Output is correct
5 Correct 340 ms 74488 KB Output is correct
6 Correct 374 ms 74472 KB Output is correct
7 Correct 349 ms 74744 KB Output is correct
8 Correct 425 ms 74488 KB Output is correct
9 Correct 274 ms 74748 KB Output is correct
10 Correct 296 ms 74616 KB Output is correct
11 Correct 243 ms 74616 KB Output is correct
12 Correct 386 ms 74616 KB Output is correct