oj.uz

Submission #50853

# Submission time Handle Problem Language Result Execution time Memory
50853 2018-06-13T17:01:19 Z faustaadp Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 2021 ms 106664 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[404040],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 24 ms 19320 KB Output is correct
2 Correct 23 ms 19812 KB Output is correct
3 Correct 30 ms 20636 KB Output is correct
4 Correct 41 ms 20636 KB Output is correct
5 Correct 61 ms 21392 KB Output is correct
6 Correct 36 ms 21536 KB Output is correct
7 Correct 41 ms 21536 KB Output is correct
8 Correct 39 ms 21588 KB Output is correct
9 Correct 48 ms 21588 KB Output is correct
10 Correct 45 ms 21588 KB Output is correct
11 Correct 45 ms 21588 KB Output is correct
12 Correct 42 ms 21676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 59616 KB Output is correct
2 Correct 455 ms 59616 KB Output is correct
3 Correct 733 ms 85292 KB Output is correct
4 Correct 851 ms 104816 KB Output is correct
5 Correct 924 ms 106040 KB Output is correct
6 Correct 1002 ms 106124 KB Output is correct
7 Correct 1031 ms 106124 KB Output is correct
8 Correct 1012 ms 106156 KB Output is correct
9 Correct 1036 ms 106156 KB Output is correct
10 Correct 963 ms 106156 KB Output is correct
11 Correct 963 ms 106156 KB Output is correct
12 Correct 1063 ms 106156 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 106156 KB Output is correct
2 Correct 179 ms 106156 KB Output is correct
3 Correct 171 ms 106156 KB Output is correct
4 Correct 183 ms 106156 KB Output is correct
5 Correct 529 ms 106156 KB Output is correct
6 Correct 499 ms 106156 KB Output is correct
7 Correct 748 ms 106156 KB Output is correct
8 Correct 496 ms 106156 KB Output is correct
9 Correct 411 ms 106156 KB Output is correct
10 Correct 493 ms 106156 KB Output is correct
11 Correct 448 ms 106156 KB Output is correct
12 Correct 428 ms 106156 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 106156 KB Output is correct
2 Correct 631 ms 106156 KB Output is correct
3 Correct 905 ms 106156 KB Output is correct
4 Correct 681 ms 106156 KB Output is correct
5 Correct 1349 ms 106280 KB Output is correct
6 Correct 1432 ms 106280 KB Output is correct
7 Correct 1548 ms 106280 KB Output is correct
8 Correct 1682 ms 106280 KB Output is correct
9 Correct 1768 ms 106280 KB Output is correct
10 Correct 1602 ms 106352 KB Output is correct
11 Correct 1298 ms 106372 KB Output is correct
12 Correct 2021 ms 106664 KB Output is correct