oj.uz

Submission #67205

# Submission time Handle Problem Language Result Execution time Memory
67205 2018-08-13T15:51:11 Z zetapi Dancing Elephants (IOI11_elephants) C++14
26 / 100
 25 ms 4248 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define ll  long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=1e5;
const int len=400;

int N,K,qcnt,pos[MAX],lol[MAX];

struct data
{
	int size;
	int arr[1000],dp[1000],right[1000];
	data()
	{
		size=0;
	}
	void cal()
	{
		int ptr=size;
		for(int A=size-1;A>=0;A--)
		{
			while(arr[ptr-1]-arr[A]>K)
				--ptr;
			if(ptr==size)
			{
				dp[A]=1;
				right[A]=arr[A]+K;
			}
			else
			{
				dp[A]=1+dp[ptr];
				right[A]=right[ptr];
			}
		}
		return ;
	}
	void insert(int val)
	{
		int B=0;
		for(int A=size-1;A>=0;A--)
		{
			if(arr[A]<=val)
			{
				B=A+1;
				break;
			}
		}
		for(int C=size;C>B;C--)
			arr[C]=arr[C-1];
		arr[B]=val;
		++size;
		return ;
	}
	void remove(int val)
	{
		for(int A=0;A<size;A++)
		{
			if(arr[A]==val)
			{
				for(int B=A;B<size-1;B++)
					arr[B]=arr[B+1];
				break;
			}
		}
		--size;
		return ;
	}
}	block[400];

void init(int n,int l,int X[])
{
	N=n;
	K=l;
	for(int A=0;A<N;A++)
	{
		pos[A]=X[A];
		block[A/len].arr[block[A/len].size]=X[A];
		block[A/len].size++;
	}
	for(int A=0;block[A].size>0;A++)
		block[A].cal();
	return ;
}

int update(int idx,int val)
{
	++qcnt;
	int B;
	for(B=0;block[B].size>0;B++)
	{
		if(block[B].arr[0]>pos[idx])
			break;
	}
	if(B)
		B--;
	block[B].remove(pos[idx]);
	block[B].cal();
	pos[idx]=val;
	for(B=0;block[B].size>0;B++)
	{
		if(block[B].arr[0]>pos[idx])
			break;
	}
	if(B)
		B--;
	block[B].insert(pos[idx]);
	block[B].cal();
	int covered=-1,res=0;
	for(int A=0;block[A].size>0;A++)
	{
		int cur=upper_bound(block[A].arr,block[A].arr+block[A].size,covered)-block[A].arr;
		if(cur==block[A].size)
			continue;
		res+=block[A].dp[cur];
		covered=block[A].right[cur];
	}
	/*for(int A=0;block[A].size>0;A++)
			for(int B=0;B<block[A].size;B++)
				cout<<block[A].arr[B]<<" ";
	cout<<"\n";*/
	if(qcnt==len-1)
	{
		int cur=0;
		for(int A=0;block[A].size>0;A++)
		{
			for(int B=0;B<block[A].size;B++)
				lol[cur++]=block[A].arr[B];
			block[A].size=0;
		}
		for(int A=0;A<cur;A++)
		{
			pos[A]=lol[A];
			block[A/len].arr[block[A/len].size]=lol[A];
			block[A/len].size++;
		}
		qcnt=0;
	}
	return res;
}

/*signed main()
{
	ios_base::sync_with_stdio(false);

	int N=4,L=10;
	int X[]={10,15,17,20};
	init(N,L,X);
	cout<<update(2,15)<<"\n";
	cout<<update(1,25)<<"\n";
	cout<<update(3,35)<<"\n";
	cout<<update(0,38)<<"\n";
	cout<<update(2,00)<<"\n";
	return 0;
}*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 5 ms 2172 KB Output is correct
3 Correct 4 ms 2240 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 5 ms 2172 KB Output is correct
3 Correct 4 ms 2240 KB Output is correct
4 Correct 5 ms 2352 KB Output is correct
5 Correct 4 ms 2444 KB Output is correct
6 Correct 4 ms 2444 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 5 ms 2172 KB Output is correct
3 Correct 4 ms 2240 KB Output is correct
4 Correct 5 ms 2352 KB Output is correct
5 Correct 4 ms 2444 KB Output is correct
6 Correct 4 ms 2444 KB Output is correct
7 Incorrect 25 ms 4248 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 5 ms 2172 KB Output is correct
3 Correct 4 ms 2240 KB Output is correct
4 Correct 5 ms 2352 KB Output is correct
5 Correct 4 ms 2444 KB Output is correct
6 Correct 4 ms 2444 KB Output is correct
7 Incorrect 25 ms 4248 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 5 ms 2172 KB Output is correct
3 Correct 4 ms 2240 KB Output is correct
4 Correct 5 ms 2352 KB Output is correct
5 Correct 4 ms 2444 KB Output is correct
6 Correct 4 ms 2444 KB Output is correct
7 Incorrect 25 ms 4248 KB Output isn't correct
8 Halted 0 ms 0 KB -