oj.uz

Submission #94076

# Submission time Handle Problem Language Result Execution time Memory
94076 2019-01-15T16:13:22 Z gumball Ball Machine (BOI13_ballmachine) C++14
100 / 100
 817 ms 39800 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,i,ta,ROOT,p[22][101010],pri[101010],nil[101010],j,te,dep[101010],q,ST[404040],LZ[404040],bes[404040],tb;
vector<ll> v[101010];
ll mi[101010];
bool cmp(ll aa,ll bb)
{
	return (mi[aa]<mi[bb]);
}
void dfs0(ll aa)
{
	mi[aa]=aa;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		dfs0(v[aa][ii]);
		mi[aa]=min(mi[aa],mi[v[aa][ii]]);
	}
	sort(v[aa].begin(),v[aa].end(),cmp);
}
void dfs(ll aa,ll bb)
{
	dep[aa]=bb;
	mi[aa]=aa;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
		dfs(v[aa][ii],bb+1);
	pri[++te]=aa;
	nil[aa]=te;
}
void bawah(ll ee)
{
	if(LZ[ee]!=-1)
	{
		ST[ee]=LZ[ee]*bes[ee];
		if(bes[ee]>1)
		{
			LZ[ee*2]=LZ[ee];
			LZ[ee*2+1]=LZ[ee];
		}
		LZ[ee]=-1;
	}
}
void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff)
{
	bes[ee]=bb-aa+1;
	bawah(ee);
	if(bb<cc||dd<aa)return ;
	else if(cc<=aa&&bb<=dd)
	{
		ST[ee]=ff*(bb-aa+1);
		if(aa<bb)
		{
			LZ[ee*2]=ff;
			LZ[ee*2+1]=ff;
		}
	}
	else
	{
		ll ce=(aa+bb)/2;
		upd(aa,ce,cc,dd,ee*2,ff);
		upd(ce+1,bb,cc,dd,ee*2+1,ff);
		ST[ee]=ST[ee*2]+ST[ee*2+1];
	}
}
ll que(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(cc==0)return 1;
	bawah(ee);
	if(bb<cc||dd<aa)return 0;
	if(cc<=aa&&bb<=dd)return ST[ee];
	else 
	{
		ll ce=(aa+bb)/2;
		return que(aa,ce,cc,dd,ee*2)+que(ce+1,bb,cc,dd,ee*2+1);
	}
}
ll cari(ll aa,ll bb,ll cc,ll ee)
{
	bawah(ee);
	if(aa==bb)return aa; 
	ll ce=(aa+bb)/2;
	if(que(1,n,aa,ce,1)>=cc)return cari(aa,ce,cc,ee*2);
	else cari(ce+1,bb,cc-que(1,n,aa,ce,1),ee*2+1);
}
int main()
{
	ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>q;
	for(i=1;i<=n;i++)
	{
		cin>>ta;
		if(ta==0)
		{
			ROOT=i;
			p[0][i]=0;
		}
		else
		{
			v[ta].pb(i);
			p[0][i]=ta;
		}
	}
	memset(LZ,-1,sizeof(LZ));
	dfs0(ROOT);
	dfs(ROOT,1);
	for(i=1;i<=20;i++)
		for(j=1;j<=n;j++)
			p[i][j]=p[i-1][p[i-1][j]];
	//for(i=1;i<=n;i++)cout<<i<<" "<<p[1][i]<<"\n";
	for(i=1;i<=n;i++)upd(1,n,i,i,1,1);
	while(q--)
	{
		cin>>ta>>tb;
		if(ta==1)
		{
			ll x=cari(1,n,tb,1);
			//cout<<x<<"\n";
			upd(1,n,1,x,1,0);
			cout<<pri[x]<<"\n";
		}
		else
		{
			//for(i=1;i<=n;i++)cout<<i<<" "<<que(1,n,i,1)<<"\n";
			ll x=0;
			for(i=20;i>=0;i--)
			{
				//cout<<i<<"  "<<tb<<" "<<p[i][tb]<<" \n";
				if(que(1,n,nil[p[i][tb]],nil[p[i][tb]],1)==0)
				{
					x+=(1<<i);
					tb=p[i][tb];
				}
			}
			cout<<x<<"\n";
			upd(1,n,nil[tb],nil[tb],1,1);
		}
	}
}

Compilation message

ballmachine.cpp: In function 'void dfs0(long long int)':
ballmachine.cpp:19:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs(long long int, long long int)':
ballmachine.cpp:31:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'long long int cari(long long int, long long int, long long int, long long int)':
ballmachine.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6136 KB Output is correct
2 Correct 321 ms 22140 KB Output is correct
3 Correct 152 ms 22296 KB Output is correct
4 Correct 6 ms 6008 KB Output is correct
5 Correct 6 ms 6136 KB Output is correct
6 Correct 7 ms 6264 KB Output is correct
7 Correct 8 ms 6264 KB Output is correct
8 Correct 8 ms 6264 KB Output is correct
9 Correct 17 ms 7032 KB Output is correct
10 Correct 44 ms 10104 KB Output is correct
11 Correct 325 ms 22176 KB Output is correct
12 Correct 150 ms 22288 KB Output is correct
13 Correct 198 ms 22108 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 12656 KB Output is correct
2 Correct 817 ms 35184 KB Output is correct
3 Correct 184 ms 31472 KB Output is correct
4 Correct 266 ms 14860 KB Output is correct
5 Correct 389 ms 14736 KB Output is correct
6 Correct 359 ms 14616 KB Output is correct
7 Correct 332 ms 13744 KB Output is correct
8 Correct 129 ms 12560 KB Output is correct
9 Correct 609 ms 35576 KB Output is correct
10 Correct 810 ms 35324 KB Output is correct
11 Correct 522 ms 35064 KB Output is correct
12 Correct 720 ms 33168 KB Output is correct
13 Correct 295 ms 36216 KB Output is correct
14 Correct 186 ms 31472 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 20984 KB Output is correct
2 Correct 756 ms 33960 KB Output is correct
3 Correct 443 ms 33656 KB Output is correct
4 Correct 355 ms 30584 KB Output is correct
5 Correct 472 ms 30464 KB Output is correct
6 Correct 477 ms 30200 KB Output is correct
7 Correct 470 ms 28920 KB Output is correct
8 Correct 454 ms 33696 KB Output is correct
9 Correct 534 ms 35704 KB Output is correct
10 Correct 628 ms 35328 KB Output is correct
11 Correct 623 ms 35420 KB Output is correct
12 Correct 657 ms 33772 KB Output is correct
13 Correct 620 ms 39800 KB Output is correct
14 Correct 247 ms 31444 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 35968 KB Output is correct
2 Correct 786 ms 33784 KB Output is correct
3 Correct 275 ms 39416 KB Output is correct
4 Correct 507 ms 35800 KB Output is correct
5 Correct 635 ms 35320 KB Output is correct
6 Correct 485 ms 35248 KB Output is correct
7 Correct 659 ms 33824 KB Output is correct
8 Correct 262 ms 39544 KB Output is correct
9 Correct 213 ms 31472 KB Output is correct