oj.uz

답안 #66621

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66621 2018-08-11T19:14:59 Z zetapi 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
10 / 100
 4 ms 576 KB 
#include<elephants.h>
 
#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=6e6;
const int ROOT=50;
 
vector<pii> blocks;
 
ll dp[MAX],BlockNumber[MAX],Index[1100][1100];
 
ll N,K,qcnt,ptr,start,pos[MAX],nxt[MAX],pre[MAX],arr[MAX];
 
void recalculate(ll idx)
{
	for(int A=1;Index[idx][A]>0;A++)
		Index[idx][A]=0;
	ll start_=blocks[idx].first,end_=blocks[idx].second,lol=start_,lop=1;
	pre[start_]=0;
	Index[idx][1]=start_;
	for(int A=nxt[start_];A!=nxt[end_];A=nxt[A])
	{
		pre[A]=lol;
		lol=A;
		Index[idx][++lop]=A;
	}
	ll cov=end_,cnt=1;
	for(int A=end_;A>0;A=pre[A])
	{
		if(arr[cov]-arr[A]>K)
		{
			cov=A;
			++cnt;
		}
		dp[A]=cnt;
	}
	/*cout<<arr[end_]<<"\n";
	for(int A=start;A>0;A=nxt[A])
		cout<<arr[A]<<" ";
	cout<<"\n";*/
	return ;
}
 
void build()
{
	blocks.clear();
	ll lol=0;
	for(int A=0;A<=ROOT;A++)
		for(int B=0;Index[A][B]>0;B++)
			Index[A][B]=0;
	for(int A=start;A>0;A=nxt[A])
	{
		BlockNumber[A]=blocks.size();
		Index[BlockNumber[A]][++lol]=A;
		if(lol==ROOT or nxt[A]==0)
		{
			blocks.pb(mp(Index[BlockNumber[A]][1],A));
			lol=0;
		}
	}
	for(int A=0;A<blocks.size();A++)
		recalculate(A);
	return ;
}
 
void remove(ll idx,ll val)
{
	if(idx==start)
	{
		start=nxt[start];
		blocks[0].first=start;
		recalculate(BlockNumber[idx]);
		return ;
	}
	for(int A=start;nxt[A]>0;A=nxt[A])
	{
		if(nxt[A]==idx)
		{
			nxt[A]=nxt[nxt[A]];
			if(idx==blocks[BlockNumber[idx]].first)
				blocks[BlockNumber[idx]].first=nxt[A];
			else if(idx==blocks[BlockNumber[idx]].second)
				blocks[BlockNumber[idx]].second=A;
			break;
		}
	}
	recalculate(BlockNumber[idx]);
	return ;
}
 
void insert(ll idx,ll val)
{
	if(val<=arr[start])
	{
		nxt[idx]=start;
		start=idx;
		BlockNumber[idx]=0;
		blocks[0].first=start;
		recalculate(BlockNumber[idx]);
	}
	else
	{
		ll lol=start;
		for(int A=start;A>0;A=nxt[A])
			if(val>=arr[A])
				lol=A;
		nxt[idx]=nxt[lol];
		nxt[lol]=idx;
		BlockNumber[idx]=BlockNumber[lol];
		if(lol==blocks[BlockNumber[lol]].second)
			blocks[BlockNumber[lol]].second=idx;
		recalculate(BlockNumber[idx]);
	}
	return ;
}
 
ll count(ll CurrentBlock,ll CoveredTill)
{
	if(CurrentBlock>=blocks.size())
		return 0;
	ll low=1,high=699,mid,res=-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(Index[CurrentBlock][mid]==0)
			high=mid-1;
		else if(arr[Index[CurrentBlock][mid]]<=CoveredTill)
			res=Index[CurrentBlock][mid],
			low=mid+1;
		else
			high=mid-1;
	}
	if(res==blocks[CurrentBlock].second)
		return count(CurrentBlock+1,CoveredTill);
	else if(res<0)
		res=blocks[CurrentBlock].first;
	else
		res=nxt[res];
	return dp[res]+count(CurrentBlock+1,arr[res]+dp[res]*K);
}
 
void init(int n,int l,int X[])
{
	N=n;
	K=l;
	ptr=n;
	start=1;
	for(int A=1;A<=N;A++)
	{
		pos[A]=A;
		nxt[A]=A+1;
		arr[A]=X[A-1];
	}
	nxt[N]=0;
	build();
  	return ;
}
 
int update(int i,int y)
{
	if(N==1)
		return 1;
	++i;
	++ptr;
	++qcnt;
	remove(pos[i],y);
	pos[i]=ptr;
	arr[ptr]=y;
	insert(pos[i],y);
//	if(qcnt%ROOT==0)
//	{
//		qcnt=0;
//		build();
//	}
  	for(int A=0;A<blocks.size()-1;A++)
  		assert(nxt[blocks[A].second]==blocks[A+1].first);
  	int cur=start;
  	for(int A=0;A<blocks.size();A++)
  	{
  		recalculate(A);
  		for(int B=1;Index[A][B]>0;B++)
  		{
  			assert(Index[A][B]==cur);
  			cur=nxt[cur];
  		}
  	}
  	assert(cur==0);
	return count(0,-1);
}

Compilation message

elephants.cpp: In function 'void build()':
elephants.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<blocks.size();A++)
              ~^~~~~~~~~~~~~~
elephants.cpp: In function 'long long int count(long long int, long long int)':
elephants.cpp:127:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(CurrentBlock>=blocks.size())
     ~~~~~~~~~~~~^~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:183:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=0;A<blocks.size()-1;A++)
                ~^~~~~~~~~~~~~~~~
elephants.cpp:186:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=0;A<blocks.size();A++)
                ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 524 KB Output is correct

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 524 KB Output is correct
4 Incorrect 3 ms 576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 524 KB Output is correct
4 Incorrect 3 ms 576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 524 KB Output is correct
4 Incorrect 3 ms 576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 524 KB Output is correct
4 Incorrect 3 ms 576 KB Output isn't correct
5 Halted 0 ms 0 KB -