oj.uz

Submission #50849

# Submission time Handle Problem Language Result Execution time Memory
50849 2018-06-13T16:54:14 Z faustaadp Sterilizing Spray (JOI15_sterilizing) C++17
25 / 100
 5000 ms 130040 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)
{
	if(a[cc]==0)
	{
		if(sT[ee].count(cc))
			sT[ee].erase(cc);
	}
	else
	{
		if(!sT[ee].count(cc))
			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);
		else
			upd(ce+1,bb,cc,ee*2+1);
		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);
	}
	while(q--)
	{
		cin>>ta;
		if(ta==1)
		{
			cin>>ta>>tb;
			a[ta]=tb;
			upd(1,n,ta,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;
	//			cout<<v[i]<<"VI\n";
				for(it=sT[v[i]].begin();it!=sT[v[i]].end();it++)
				{
					tem.pb(*it);
	//				cout<<*it<<"IT\n";
					a[*it]=a[*it]/k;
	//				cout<<*it<<" "<<a[*it]<<" "<<a[*it]/k<<"\n";
				}	
				for(j=0;j<tem.size();j++)
					upd(1,n,tem[j],1);				
			}
		}
		else
		{
			cin>>ta>>tb;
			cout<<jum(1,n,ta,tb,1)<<"\n";
		}
	}
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:89:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++)
            ~^~~~~~~~~
sterilizing.cpp:100: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 19448 KB Output is correct
2 Correct 21 ms 19840 KB Output is correct
3 Correct 36 ms 20696 KB Output is correct
4 Correct 62 ms 20696 KB Output is correct
5 Correct 71 ms 21828 KB Output is correct
6 Correct 58 ms 21828 KB Output is correct
7 Correct 63 ms 21828 KB Output is correct
8 Correct 72 ms 21828 KB Output is correct
9 Correct 74 ms 21828 KB Output is correct
10 Correct 67 ms 21828 KB Output is correct
11 Correct 107 ms 21828 KB Output is correct
12 Correct 82 ms 21828 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 60616 KB Output is correct
2 Correct 461 ms 60616 KB Output is correct
3 Correct 695 ms 86344 KB Output is correct
4 Correct 885 ms 105728 KB Output is correct
5 Correct 971 ms 107008 KB Output is correct
6 Correct 1016 ms 107040 KB Output is correct
7 Correct 1128 ms 107200 KB Output is correct
8 Correct 1136 ms 107200 KB Output is correct
9 Correct 943 ms 107200 KB Output is correct
10 Correct 1049 ms 107264 KB Output is correct
11 Correct 973 ms 107264 KB Output is correct
12 Correct 924 ms 107264 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 107264 KB Output is correct
2 Correct 147 ms 107264 KB Output is correct
3 Correct 164 ms 107264 KB Output is correct
4 Correct 187 ms 107264 KB Output is correct
5 Correct 483 ms 107264 KB Output is correct
6 Correct 509 ms 107264 KB Output is correct
7 Correct 673 ms 107264 KB Output is correct
8 Correct 445 ms 107264 KB Output is correct
9 Correct 481 ms 107264 KB Output is correct
10 Correct 412 ms 107264 KB Output is correct
11 Correct 414 ms 107264 KB Output is correct
12 Correct 463 ms 107264 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1418 ms 107264 KB Output is correct
2 Correct 1442 ms 107264 KB Output is correct
3 Correct 2855 ms 107264 KB Output is correct
4 Correct 1380 ms 107264 KB Output is correct
5 Correct 2562 ms 114052 KB Output is correct
6 Correct 3158 ms 116708 KB Output is correct
7 Correct 2612 ms 119004 KB Output is correct
8 Correct 4407 ms 121656 KB Output is correct
9 Correct 3528 ms 123948 KB Output is correct
10 Correct 4387 ms 126332 KB Output is correct
11 Correct 2984 ms 128660 KB Output is correct
12 Execution timed out 5033 ms 130040 KB Time limit exceeded