oj.uz

답안 #239928

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239928 2020-06-17T14:03:17 Z MvC Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 721 ms 71800 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int n,q,l,r,a[nmax],k,lzy[4*nmax],tp,i;
ll st[4*nmax],vl[4*nmax][32],fw[nmax];
void push(int nod,int l,int r)
{
    if(!lzy[nod])return;
    lzy[nod]=min(lzy[nod],30);
    int i;
    for(i=0;i+lzy[nod]<=30;i++)vl[nod][i]=vl[nod][i+lzy[nod]];
    for(;i<=30;i++)vl[nod][i]=0;
    ll pw=1;
    st[nod]=0;
    for(i=0;i<=30;i++)
    {
		st[nod]+=pw*vl[nod][i];
		if(pw*1LL*k>=inf)break;
		pw*=k;
	}
    if(l!=r)
    {
    	lzy[nod*2]+=lzy[nod];
		lzy[nod*2+1]+=lzy[nod];
	}
    lzy[nod]=0;
}
void upd(int nod,int l,int r,int tl,int tr)
{
    push(nod,l,r);
    if(tl<=l && r<=tr)
	{
        lzy[nod]++;
        push(nod,l,r);
        return;
    }
    int mid=(l+r)/2;
    if(tl<=mid)upd(nod*2,l,mid,tl,tr);
    if(mid<tr)upd(nod*2+1,mid+1,r,tl,tr);
    push(nod*2,l,mid);
	push(nod*2+1,mid+1,r);
	for(int i=0;i<=30;i++)vl[nod][i]=vl[nod*2][i]+vl[nod*2+1][i];
    st[nod]=st[nod*2]+st[nod*2+1];
}
void chg(int nod,int l,int r,int p,int v)
{
    push(nod,l,r);
    if(l==r)
	{
		st[nod]=v;
		int i=0;
        while(v)
        {
			vl[nod][i++]=v%k;
			v/=k;
		}
		for(;i<=30;i++)vl[nod][i]=0;
        return;
    }
    int mid=(l+r)/2;
    if(p<=mid)chg(nod*2,l,mid,p,v);
    else chg(nod*2+1,mid+1,r,p,v);
    push(nod*2,l,mid);
	push(nod*2+1,mid+1,r);
	for(int i=0;i<=30;i++)vl[nod][i]=vl[nod*2][i]+vl[nod*2+1][i];
    st[nod]=st[nod*2]+st[nod*2+1];
}
ll qry(int nod,int l,int r,int tl,int tr)
{
    push(nod,l,r);
    if(l>tr || r<tl)return 0;
    if(tl<=l && r<=tr)return st[nod];
    int mid=(l+r)/2;
    return qry(nod*2,l,mid,tl,tr)+qry(nod*2+1,mid+1,r,tl,tr);
}
void ufw(int i,ll v)
{
	for(;i<=n;i+=i&(-i))fw[i]+=v;
}
ll qfw(int i)
{
	ll ans=0;
	for(;i>=1;i-=i&(-i))ans+=fw[i];
	return ans;
}
ll query(int l,int r)
{
	ll ans=qfw(r);
	if(l>1)ans-=qfw(l-1);
	return ans;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>q>>k;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		if(k!=1)chg(1,1,n,i,a[i]);
		else ufw(i,a[i]);
	}
	while(q--)
	{
		cin>>tp>>l>>r;
		if(tp==1)
		{
			if(k!=1)
			{
				a[l]=r;
				chg(1,1,n,l,a[l]);
			}
			else
			{
				ufw(l,-a[l]);
				a[l]=r;
				ufw(l,a[l]);
			}
		}
		else if(tp==2 && k!=1)upd(1,1,n,l,r);
		else if(tp==3)
		{
			if(k==1)cout<<query(l,r)<<'\n';
			else cout<<qry(1,1,n,l,r)<<'\n';
		}
	}
	return 0;
}
/*
5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5
*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 1408 KB Output is correct
4 Correct 13 ms 1536 KB Output is correct
5 Correct 15 ms 2560 KB Output is correct
6 Correct 16 ms 2560 KB Output is correct
7 Correct 13 ms 2560 KB Output is correct
8 Correct 12 ms 2560 KB Output is correct
9 Correct 13 ms 2560 KB Output is correct
10 Correct 13 ms 2560 KB Output is correct
11 Correct 12 ms 2560 KB Output is correct
12 Correct 13 ms 2560 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 1528 KB Output is correct
2 Correct 40 ms 1272 KB Output is correct
3 Correct 39 ms 1656 KB Output is correct
4 Correct 54 ms 2040 KB Output is correct
5 Correct 56 ms 2168 KB Output is correct
6 Correct 62 ms 2172 KB Output is correct
7 Correct 54 ms 2132 KB Output is correct
8 Correct 54 ms 2168 KB Output is correct
9 Correct 52 ms 2168 KB Output is correct
10 Correct 52 ms 2168 KB Output is correct
11 Correct 55 ms 2172 KB Output is correct
12 Correct 58 ms 2356 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 4856 KB Output is correct
2 Correct 112 ms 35064 KB Output is correct
3 Correct 121 ms 35064 KB Output is correct
4 Correct 331 ms 17784 KB Output is correct
5 Correct 482 ms 69752 KB Output is correct
6 Correct 569 ms 69624 KB Output is correct
7 Correct 43 ms 1784 KB Output is correct
8 Correct 492 ms 69756 KB Output is correct
9 Correct 320 ms 69752 KB Output is correct
10 Correct 344 ms 69900 KB Output is correct
11 Correct 352 ms 69624 KB Output is correct
12 Correct 353 ms 69624 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 343 ms 35192 KB Output is correct
2 Correct 316 ms 36856 KB Output is correct
3 Correct 284 ms 36284 KB Output is correct
4 Correct 379 ms 19840 KB Output is correct
5 Correct 528 ms 71800 KB Output is correct
6 Correct 598 ms 71672 KB Output is correct
7 Correct 613 ms 71668 KB Output is correct
8 Correct 721 ms 71668 KB Output is correct
9 Correct 387 ms 71672 KB Output is correct
10 Correct 429 ms 71748 KB Output is correct
11 Correct 355 ms 71720 KB Output is correct
12 Correct 474 ms 71700 KB Output is correct