oj.uz

Submission #239916

# Submission time Handle Problem Language Result Execution time Memory
239916 2020-06-17T13:51:52 Z MvC Sterilizing Spray (JOI15_sterilizing) C++11
20 / 100
 584 ms 69784 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;
		}
        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 384 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 1428 KB Output is correct
2 Correct 44 ms 1144 KB Output is correct
3 Correct 40 ms 1528 KB Output is correct
4 Correct 51 ms 1912 KB Output is correct
5 Correct 59 ms 2040 KB Output is correct
6 Correct 59 ms 2044 KB Output is correct
7 Correct 67 ms 2040 KB Output is correct
8 Correct 59 ms 2040 KB Output is correct
9 Correct 56 ms 2168 KB Output is correct
10 Correct 58 ms 2168 KB Output is correct
11 Correct 54 ms 2040 KB Output is correct
12 Correct 55 ms 2040 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 4736 KB Output is correct
2 Correct 102 ms 34936 KB Output is correct
3 Correct 143 ms 34936 KB Output is correct
4 Correct 363 ms 17664 KB Output is correct
5 Correct 482 ms 69624 KB Output is correct
6 Correct 584 ms 69596 KB Output is correct
7 Correct 45 ms 1784 KB Output is correct
8 Correct 562 ms 69628 KB Output is correct
9 Correct 316 ms 69496 KB Output is correct
10 Correct 320 ms 69600 KB Output is correct
11 Correct 319 ms 69596 KB Output is correct
12 Correct 337 ms 69784 KB Output is correct

Subtask #4
0 / 75.0

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