oj.uz

답안 #288903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
288903 2020-09-02T06:43:47 Z YJU Sterilizing Spray (JOI15_sterilizing) C++14
90 / 100
 560 ms 75896 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,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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 7 ms 1536 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 7 ms 2688 KB Output is correct
8 Correct 7 ms 2688 KB Output is correct
9 Correct 8 ms 2688 KB Output is correct
10 Correct 7 ms 2688 KB Output is correct
11 Correct 7 ms 2688 KB Output is correct
12 Correct 7 ms 2816 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 282 ms 38136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 4992 KB Output is correct
2 Correct 95 ms 37368 KB Output is correct
3 Correct 96 ms 37240 KB Output is correct
4 Correct 188 ms 18936 KB Output is correct
5 Correct 403 ms 74268 KB Output is correct
6 Correct 560 ms 74360 KB Output is correct
7 Correct 392 ms 75896 KB Output is correct
8 Correct 371 ms 75768 KB Output is correct
9 Correct 247 ms 75640 KB Output is correct
10 Correct 259 ms 75512 KB Output is correct
11 Correct 245 ms 75512 KB Output is correct
12 Correct 272 ms 75512 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 37496 KB Output is correct
2 Correct 225 ms 37496 KB Output is correct
3 Correct 237 ms 37368 KB Output is correct
4 Correct 239 ms 19064 KB Output is correct
5 Correct 361 ms 74488 KB Output is correct
6 Correct 397 ms 74488 KB Output is correct
7 Correct 374 ms 74528 KB Output is correct
8 Correct 459 ms 74616 KB Output is correct
9 Correct 307 ms 74616 KB Output is correct
10 Correct 341 ms 74616 KB Output is correct
11 Correct 256 ms 74488 KB Output is correct
12 Correct 433 ms 74632 KB Output is correct