oj.uz

답안 #123792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123792 2019-07-02T06:56:34 Z baluteshih 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
10 / 100
 9 ms 5884 KB 
#include "elephants.h"
#include<bits/stdc++.h>
#define MP make_pair
#define F first
#define S second
#define pb push_back
#define MEM(i,j) memset(i,j,sizeof i)
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct mode
{
	int p,dp,out,i;
	list<int>::iterator bln;
};

const int B=4,block_num=200000;
int n,Len;
vector<mode> block[block_num];
vector<mode>::iterator pl[1500005];
queue<int> q;
list<int> ls;

void print()
{
	return;
	int cnt=0;
	for(auto p=ls.begin();p!=ls.end();++p)
	{
		cout << "Block " << ++cnt << "\n";
		for(auto i:block[*p])
			cout << "{" << i.p << "," << i.dp << "," << i.out << "} ";
		ET; 
	}
	ET;
}

int nwblock()
{
	int x=q.front();
	return q.pop(),x;
}

void merge(int i,int j)//j into i
{
	vector<mode> tmp;
	for(int a=0,b=0;a<block[i].size()||b<block[i].size();)
		if(a<block[i].size()&&(b==block[i].size()||block[i][a].p<block[j][b].p))
			tmp.pb(block[i][a++]);
		else
			tmp.pb(block[j][b++]);
	tmp.swap(block[i]),vector<mode>().swap(block[j]),q.push(j);
}

void rebuild(list<int>::iterator it)
{
	if(block[*it].size()>2*B)
	{
		ls.insert(it,nwblock());
		while(block[*it].size()>B)
			block[*prev(it)].pb(block[*it].back()),block[*it].pop_back();
		reverse(ALL(block[*prev(it)])),swap(*it,*prev(it));
		rebuild(it),rebuild(prev(it));
		return;
	}
	if(block[*it].size()*2<B&&next(it)!=ls.end())
	{
		merge(*it,*next(it)),ls.erase(next(it)),rebuild(it);
		return;
	}
	for(int i=block[*it].size()-1,j=block[*it].size();i>=0;--i)
	{
		while(j>0&&block[*it][j-1].p>block[*it][i].p+Len) --j;
		if(j==block[*it].size())
			block[*it][i].dp=1,block[*it][i].out=block[*it][i].p+Len;
		else
			block[*it][i].dp=block[*it][j].dp+1,block[*it][i].out=block[*it][j].out;
		block[*it][i].bln=it,pl[block[*it][i].i]=block[*it].begin()+i;
	}
}

void init(int N, int L, int X[])
{
	Len=L;
	for(int i=0;i<block_num;++i)
		q.push(i);
	int nw=-1;
	for(int i=0;i<N;++i)
	{
		if(!~nw||block[nw].size()==B)
			nw=nwblock(),ls.pb(nw);
		block[nw].pb(mode{X[i],0,0,i,--ls.end()});
	}
	for(auto p=ls.begin();p!=ls.end();++p)
		rebuild(p);
	print();
}

bool yee(int a,mode x)
{
	return a<x.p;
}

int answer()
{
	int nw=-1,ans=0;
	for(auto p=ls.begin();p!=ls.end();++p)
	{
		auto t=upper_bound(ALL(block[*p]),nw,yee);
		if(t!=block[*p].end())
			ans+=t->dp,nw=t->out;
	}
	return ans;
}

int update(int i, int y)
{
	auto it=pl[i]->bln;
	block[*it].erase(pl[i]),rebuild(it);
	if(y>block[*--ls.end()].back().p)
		block[*--ls.end()].pb(mode{y,0,0,i,--ls.end()}),rebuild(--ls.end());
	else
		for(auto p=ls.begin();p!=ls.end();++p)
		{
			if(block[*p].back().p<y) continue;
			block[*p].pb(mode{y,0,0,i,p});
			for(int i=block[*p].size()-1;i>0;--i)
				if(block[*p][i].p<block[*p][i-1].p)
					swap(block[*p][i],block[*p][i-1]);
			rebuild(p);
			break;
		}
	print();
	return answer();
}

Compilation message

elephants.cpp: In function 'void merge(int, int)':
elephants.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int a=0,b=0;a<block[i].size()||b<block[i].size();)
                  ~^~~~~~~~~~~~~~~~
elephants.cpp:52:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int a=0,b=0;a<block[i].size()||b<block[i].size();)
                                     ~^~~~~~~~~~~~~~~~
elephants.cpp:53:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(a<block[i].size()&&(b==block[i].size()||block[i][a].p<block[j][b].p))
      ~^~~~~~~~~~~~~~~~
elephants.cpp:53:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(a<block[i].size()&&(b==block[i].size()||block[i][a].p<block[j][b].p))
                          ~^~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void rebuild(std::__cxx11::list<int>::iterator)':
elephants.cpp:79:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j==block[*it].size())
      ~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 9 ms 5884 KB Output is correct

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 9 ms 5884 KB Output is correct
4 Incorrect 7 ms 5880 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 9 ms 5884 KB Output is correct
4 Incorrect 7 ms 5880 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 9 ms 5884 KB Output is correct
4 Incorrect 7 ms 5880 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 9 ms 5884 KB Output is correct
4 Incorrect 7 ms 5880 KB Output isn't correct
5 Halted 0 ms 0 KB -