oj.uz

Submission #288904

# Submission time Handle Problem Language Result Execution time Memory
288904 2020-09-02T06:47:55 Z YJU Sterilizing Spray (JOI15_sterilizing) C++14
90 / 100
 534 ms 74616 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){
		tag[id*2]+=tag[id];tag[id*2+1]+=tag[id];
		tag[id]=0;
		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,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||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 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 7 ms 2688 KB Output is correct
8 Correct 6 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 7 ms 2688 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 37752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4992 KB Output is correct
2 Correct 92 ms 37240 KB Output is correct
3 Correct 99 ms 37240 KB Output is correct
4 Correct 188 ms 18936 KB Output is correct
5 Correct 397 ms 74232 KB Output is correct
6 Correct 534 ms 74232 KB Output is correct
7 Correct 393 ms 74360 KB Output is correct
8 Correct 367 ms 74300 KB Output is correct
9 Correct 235 ms 74360 KB Output is correct
10 Correct 255 ms 74360 KB Output is correct
11 Correct 242 ms 74232 KB Output is correct
12 Correct 273 ms 74260 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 37416 KB Output is correct
2 Correct 228 ms 37624 KB Output is correct
3 Correct 232 ms 37432 KB Output is correct
4 Correct 233 ms 19064 KB Output is correct
5 Correct 360 ms 74616 KB Output is correct
6 Correct 387 ms 74616 KB Output is correct
7 Correct 371 ms 74616 KB Output is correct
8 Correct 451 ms 74616 KB Output is correct
9 Correct 296 ms 74616 KB Output is correct
10 Correct 314 ms 74600 KB Output is correct
11 Correct 263 ms 74488 KB Output is correct
12 Correct 410 ms 74616 KB Output is correct