oj.uz

Submission #288902

# Submission time Handle Problem Language Result Execution time Memory
288902 2020-09-02T06:41:41 Z YJU Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 549 ms 524292 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(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,32)if(p[i]>1e9)break;else 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){
		++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)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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Runtime error 330 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 325 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5368 KB Output is correct
2 Correct 96 ms 37656 KB Output is correct
3 Correct 100 ms 37752 KB Output is correct
4 Correct 204 ms 19576 KB Output is correct
5 Correct 400 ms 75000 KB Output is correct
6 Correct 549 ms 74872 KB Output is correct
7 Runtime error 329 ms 524292 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 37804 KB Output is correct
2 Correct 228 ms 38136 KB Output is correct
3 Correct 238 ms 38008 KB Output is correct
4 Correct 240 ms 19704 KB Output is correct
5 Correct 362 ms 75128 KB Output is correct
6 Correct 404 ms 75128 KB Output is correct
7 Correct 368 ms 75256 KB Output is correct
8 Correct 459 ms 75128 KB Output is correct
9 Correct 297 ms 75256 KB Output is correct
10 Correct 333 ms 75256 KB Output is correct
11 Correct 265 ms 75128 KB Output is correct
12 Correct 440 ms 75256 KB Output is correct