oj.uz

Submission #123808

# Submission time Handle Problem Language Result Execution time Memory
123808 2019-07-02T07:14:16 Z baluteshih Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5627 ms 23172 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=400,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[j].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].empty())
		return q.push(*it),ls.erase(it),void();
	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));
	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]);
				else break;
			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[j].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[j].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:78:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j==block[*it].size())
      ~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 8 ms 5852 KB Output is correct
5 Correct 8 ms 5880 KB Output is correct
6 Correct 7 ms 5880 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 8 ms 5852 KB Output is correct
5 Correct 8 ms 5880 KB Output is correct
6 Correct 7 ms 5880 KB Output is correct
7 Correct 1184 ms 7884 KB Output is correct
8 Correct 1212 ms 8080 KB Output is correct
9 Correct 1089 ms 9380 KB Output is correct
10 Correct 1198 ms 10912 KB Output is correct
11 Correct 1245 ms 11020 KB Output is correct
12 Correct 1466 ms 10252 KB Output is correct
13 Correct 1204 ms 10884 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 8 ms 5852 KB Output is correct
5 Correct 8 ms 5880 KB Output is correct
6 Correct 7 ms 5880 KB Output is correct
7 Correct 1184 ms 7884 KB Output is correct
8 Correct 1212 ms 8080 KB Output is correct
9 Correct 1089 ms 9380 KB Output is correct
10 Correct 1198 ms 10912 KB Output is correct
11 Correct 1245 ms 11020 KB Output is correct
12 Correct 1466 ms 10252 KB Output is correct
13 Correct 1204 ms 10884 KB Output is correct
14 Correct 1626 ms 8704 KB Output is correct
15 Correct 1425 ms 8568 KB Output is correct
16 Correct 1965 ms 9604 KB Output is correct
17 Correct 2047 ms 11116 KB Output is correct
18 Correct 2154 ms 11436 KB Output is correct
19 Correct 1747 ms 12468 KB Output is correct
20 Correct 2024 ms 11156 KB Output is correct
21 Correct 2088 ms 11744 KB Output is correct
22 Correct 1761 ms 12668 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 8 ms 5852 KB Output is correct
5 Correct 8 ms 5880 KB Output is correct
6 Correct 7 ms 5880 KB Output is correct
7 Correct 1184 ms 7884 KB Output is correct
8 Correct 1212 ms 8080 KB Output is correct
9 Correct 1089 ms 9380 KB Output is correct
10 Correct 1198 ms 10912 KB Output is correct
11 Correct 1245 ms 11020 KB Output is correct
12 Correct 1466 ms 10252 KB Output is correct
13 Correct 1204 ms 10884 KB Output is correct
14 Correct 1626 ms 8704 KB Output is correct
15 Correct 1425 ms 8568 KB Output is correct
16 Correct 1965 ms 9604 KB Output is correct
17 Correct 2047 ms 11116 KB Output is correct
18 Correct 2154 ms 11436 KB Output is correct
19 Correct 1747 ms 12468 KB Output is correct
20 Correct 2024 ms 11156 KB Output is correct
21 Correct 2088 ms 11744 KB Output is correct
22 Correct 1761 ms 12668 KB Output is correct
23 Correct 4728 ms 14740 KB Output is correct
24 Correct 4811 ms 14736 KB Output is correct
25 Correct 4407 ms 15000 KB Output is correct
26 Correct 4766 ms 19328 KB Output is correct
27 Correct 4877 ms 19488 KB Output is correct
28 Correct 4257 ms 10952 KB Output is correct
29 Correct 4105 ms 11112 KB Output is correct
30 Correct 4262 ms 11000 KB Output is correct
31 Correct 4108 ms 11092 KB Output is correct
32 Correct 5222 ms 22628 KB Output is correct
33 Correct 5100 ms 22060 KB Output is correct
34 Correct 4568 ms 22800 KB Output is correct
35 Correct 5163 ms 19040 KB Output is correct
36 Correct 5361 ms 21040 KB Output is correct
37 Correct 5627 ms 20828 KB Output is correct
38 Correct 4603 ms 21980 KB Output is correct
39 Correct 4494 ms 23172 KB Output is correct
40 Correct 4806 ms 21952 KB Output is correct
41 Correct 5600 ms 19656 KB Output is correct
42 Correct 5499 ms 19584 KB Output is correct