oj.uz

Submission #50852

# Submission time Handle Problem Language Result Execution time Memory
50852 2018-06-13T17:00:38 Z faustaadp Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 1132 ms 106400 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,q,k,i,a[101010],ta,tb,ST[404040],j,v[22],te;
set<ll> sT[404040];
set<ll>::iterator it;
void upd(ll aa,ll bb,ll cc,ll ee,ll ff)
{
	if(a[cc]==0)
	{
		if(sT[ee].count(cc))
			sT[ee].erase(cc);
	}
	else
	if(ff==1)
		sT[ee].insert(cc);
	if(aa==bb)
		ST[ee]=a[cc];
	else
	{
		ll ce=(aa+bb)/2;
		if(cc<=ce)
			upd(aa,ce,cc,ee*2,ff);
		else
			upd(ce+1,bb,cc,ee*2+1,ff);
		ST[ee]=ST[ee*2]+ST[ee*2+1];
	}
}
void cari(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(bb<cc||dd<aa)
		return ;
	else
	if(cc<=aa&&bb<=dd)
	{
		te++;
		v[te]=ee;
	}
	else
	{
		ll ce=(aa+bb)/2;
		cari(aa,ce,cc,dd,ee*2);
		cari(ce+1,bb,cc,dd,ee*2+1);
	}
}
ll jum(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(bb<cc||dd<aa)
		return 0;
	else
	if(cc<=aa&&bb<=dd)
		return ST[ee];
	else
	{
		ll ce=(aa+bb)/2;
		return jum(aa,ce,cc,dd,ee*2)+jum(ce+1,bb,cc,dd,ee*2+1);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q>>k;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		upd(1,n,i,1,1);
	}
	while(q--)
	{
		cin>>ta;
		if(ta==1)
		{
			cin>>ta>>tb;
			a[ta]=tb;
			upd(1,n,ta,1,1);
		}
		else
		if(ta==2)
		{
			cin>>ta>>tb;
			if(k==1)
				continue;
			te=0;
			cari(1,n,ta,tb,1);
			for(i=1;i<=te;i++)
			{
				vector<ll> tem;
				for(it=sT[v[i]].begin();it!=sT[v[i]].end();it++)
				{
					tem.pb(*it);
					a[*it]=a[*it]/k;
				}	
				for(j=0;j<tem.size();j++)
					upd(1,n,tem[j],1,0);				
			}
		}
		else
		{
			cin>>ta>>tb;
			cout<<jum(1,n,ta,tb,1)<<"\n";
		}
	}
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:97:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<tem.size();j++)
             ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19448 KB Output is correct
2 Correct 23 ms 19936 KB Output is correct
3 Correct 28 ms 20640 KB Output is correct
4 Correct 49 ms 20640 KB Output is correct
5 Correct 59 ms 21356 KB Output is correct
6 Correct 49 ms 21452 KB Output is correct
7 Correct 57 ms 21452 KB Output is correct
8 Correct 52 ms 21480 KB Output is correct
9 Correct 51 ms 21480 KB Output is correct
10 Correct 49 ms 21496 KB Output is correct
11 Correct 50 ms 21496 KB Output is correct
12 Correct 57 ms 21608 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 59628 KB Output is correct
2 Correct 448 ms 59628 KB Output is correct
3 Correct 823 ms 85416 KB Output is correct
4 Correct 1124 ms 104864 KB Output is correct
5 Correct 1037 ms 106400 KB Output is correct
6 Correct 937 ms 106400 KB Output is correct
7 Correct 1044 ms 106400 KB Output is correct
8 Correct 1105 ms 106400 KB Output is correct
9 Correct 1128 ms 106400 KB Output is correct
10 Correct 1132 ms 106400 KB Output is correct
11 Correct 1061 ms 106400 KB Output is correct
12 Correct 912 ms 106400 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 106400 KB Output is correct
2 Correct 145 ms 106400 KB Output is correct
3 Correct 166 ms 106400 KB Output is correct
4 Correct 215 ms 106400 KB Output is correct
5 Correct 418 ms 106400 KB Output is correct
6 Incorrect 501 ms 106400 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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