oj.uz

Submission #239915

# Submission time Handle Problem Language Result Execution time Memory
239915 2020-06-17T13:47:25 Z MvC Sterilizing Spray (JOI15_sterilizing) C++11
20 / 100
 628 ms 71160 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);
    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;
		}
        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
0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3320 KB Output is correct
2 Correct 42 ms 2808 KB Output is correct
3 Correct 38 ms 3192 KB Output is correct
4 Correct 50 ms 3704 KB Output is correct
5 Correct 55 ms 3832 KB Output is correct
6 Correct 58 ms 3832 KB Output is correct
7 Correct 56 ms 3832 KB Output is correct
8 Correct 61 ms 3832 KB Output is correct
9 Correct 53 ms 3832 KB Output is correct
10 Correct 53 ms 3832 KB Output is correct
11 Correct 51 ms 3832 KB Output is correct
12 Correct 54 ms 3832 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 5240 KB Output is correct
2 Correct 111 ms 35208 KB Output is correct
3 Correct 114 ms 35320 KB Output is correct
4 Correct 300 ms 19104 KB Output is correct
5 Correct 525 ms 71160 KB Output is correct
6 Correct 628 ms 71032 KB Output is correct
7 Correct 47 ms 3192 KB Output is correct
8 Correct 444 ms 71032 KB Output is correct
9 Correct 305 ms 70904 KB Output is correct
10 Correct 309 ms 70776 KB Output is correct
11 Correct 300 ms 70780 KB Output is correct
12 Correct 319 ms 70904 KB Output is correct

Subtask #4
0 / 75.0

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