oj.uz

Submission #288901

# Submission time Handle Problem Language Result Execution time Memory
288901 2020-09-02T06:40:56 Z YJU Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 562 ms 228860 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=1e5+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 384 KB Output is correct
2 Runtime error 209 ms 228860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 208 ms 228856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4992 KB Output is correct
2 Correct 108 ms 37624 KB Output is correct
3 Correct 92 ms 37756 KB Output is correct
4 Correct 186 ms 20088 KB Output is correct
5 Correct 391 ms 75804 KB Output is correct
6 Correct 562 ms 75676 KB Output is correct
7 Runtime error 221 ms 228856 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 37496 KB Output is correct
2 Correct 221 ms 39160 KB Output is correct
3 Correct 238 ms 38648 KB Output is correct
4 Correct 238 ms 20856 KB Output is correct
5 Correct 351 ms 77048 KB Output is correct
6 Correct 385 ms 77140 KB Output is correct
7 Correct 353 ms 77080 KB Output is correct
8 Correct 460 ms 77132 KB Output is correct
9 Correct 306 ms 76920 KB Output is correct
10 Correct 324 ms 76920 KB Output is correct
11 Correct 257 ms 76960 KB Output is correct
12 Correct 433 ms 76920 KB Output is correct