oj.uz

Submission #50851

# Submission time Handle Problem Language Result Execution time Memory
50851 2018-06-13T16:59:39 Z faustaadp Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 2646 ms 107768 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;
vector<ll> v;
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)
		v.pb(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;
			v.clear();
			cari(1,n,ta,tb,1);
			for(i=0;i<v.size();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:87:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++)
            ~^~~~~~~~~
sterilizing.cpp:95: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 19320 KB Output is correct
2 Correct 22 ms 19780 KB Output is correct
3 Correct 30 ms 20380 KB Output is correct
4 Correct 37 ms 20380 KB Output is correct
5 Correct 42 ms 21452 KB Output is correct
6 Correct 35 ms 21472 KB Output is correct
7 Correct 38 ms 21472 KB Output is correct
8 Correct 40 ms 21528 KB Output is correct
9 Correct 47 ms 21532 KB Output is correct
10 Correct 38 ms 21548 KB Output is correct
11 Correct 42 ms 21676 KB Output is correct
12 Correct 39 ms 21676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 59580 KB Output is correct
2 Correct 406 ms 59580 KB Output is correct
3 Correct 648 ms 85300 KB Output is correct
4 Correct 847 ms 104704 KB Output is correct
5 Correct 1104 ms 106064 KB Output is correct
6 Correct 940 ms 106104 KB Output is correct
7 Correct 866 ms 106104 KB Output is correct
8 Correct 924 ms 106104 KB Output is correct
9 Correct 867 ms 106104 KB Output is correct
10 Correct 947 ms 106104 KB Output is correct
11 Correct 968 ms 106104 KB Output is correct
12 Correct 927 ms 106164 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 106164 KB Output is correct
2 Correct 152 ms 106164 KB Output is correct
3 Correct 163 ms 106164 KB Output is correct
4 Correct 182 ms 106164 KB Output is correct
5 Correct 456 ms 106164 KB Output is correct
6 Correct 447 ms 106164 KB Output is correct
7 Correct 734 ms 106164 KB Output is correct
8 Correct 546 ms 106164 KB Output is correct
9 Correct 381 ms 106164 KB Output is correct
10 Correct 378 ms 106164 KB Output is correct
11 Correct 391 ms 106164 KB Output is correct
12 Correct 407 ms 106164 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 106164 KB Output is correct
2 Correct 647 ms 106164 KB Output is correct
3 Correct 1110 ms 106164 KB Output is correct
4 Correct 763 ms 106164 KB Output is correct
5 Correct 1392 ms 106164 KB Output is correct
6 Correct 1632 ms 106164 KB Output is correct
7 Correct 1446 ms 106164 KB Output is correct
8 Correct 1687 ms 106276 KB Output is correct
9 Correct 1443 ms 106404 KB Output is correct
10 Correct 1830 ms 106404 KB Output is correct
11 Correct 1416 ms 106404 KB Output is correct
12 Correct 2646 ms 107768 KB Output is correct