oj.uz

Submission #123802

# Submission time Handle Problem Language Result Execution time Memory
123802 2019-07-02T07:07:33 Z baluteshih Dancing Elephants (IOI11_elephants) C++14
97 / 100
 4764 ms 23368 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].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]);
				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:79: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 9 ms 5884 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 13 ms 5880 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5884 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 13 ms 5880 KB Output is correct
4 Correct 8 ms 5880 KB Output is correct
5 Correct 8 ms 5884 KB Output is correct
6 Correct 9 ms 5880 KB Output is correct
7 Correct 1185 ms 8136 KB Output is correct
8 Correct 1214 ms 8440 KB Output is correct
9 Correct 1074 ms 10232 KB Output is correct
10 Correct 1180 ms 11480 KB Output is correct
11 Correct 1242 ms 11524 KB Output is correct
12 Correct 1459 ms 10868 KB Output is correct
13 Correct 1202 ms 11256 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5884 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 13 ms 5880 KB Output is correct
4 Correct 8 ms 5880 KB Output is correct
5 Correct 8 ms 5884 KB Output is correct
6 Correct 9 ms 5880 KB Output is correct
7 Correct 1185 ms 8136 KB Output is correct
8 Correct 1214 ms 8440 KB Output is correct
9 Correct 1074 ms 10232 KB Output is correct
10 Correct 1180 ms 11480 KB Output is correct
11 Correct 1242 ms 11524 KB Output is correct
12 Correct 1459 ms 10868 KB Output is correct
13 Correct 1202 ms 11256 KB Output is correct
14 Correct 1616 ms 9596 KB Output is correct
15 Correct 1439 ms 9244 KB Output is correct
16 Correct 1929 ms 10656 KB Output is correct
17 Correct 1982 ms 12640 KB Output is correct
18 Correct 2106 ms 12536 KB Output is correct
19 Correct 1741 ms 11896 KB Output is correct
20 Correct 1987 ms 12408 KB Output is correct
21 Correct 2092 ms 12924 KB Output is correct
22 Correct 1764 ms 13548 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5884 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 13 ms 5880 KB Output is correct
4 Correct 8 ms 5880 KB Output is correct
5 Correct 8 ms 5884 KB Output is correct
6 Correct 9 ms 5880 KB Output is correct
7 Correct 1185 ms 8136 KB Output is correct
8 Correct 1214 ms 8440 KB Output is correct
9 Correct 1074 ms 10232 KB Output is correct
10 Correct 1180 ms 11480 KB Output is correct
11 Correct 1242 ms 11524 KB Output is correct
12 Correct 1459 ms 10868 KB Output is correct
13 Correct 1202 ms 11256 KB Output is correct
14 Correct 1616 ms 9596 KB Output is correct
15 Correct 1439 ms 9244 KB Output is correct
16 Correct 1929 ms 10656 KB Output is correct
17 Correct 1982 ms 12640 KB Output is correct
18 Correct 2106 ms 12536 KB Output is correct
19 Correct 1741 ms 11896 KB Output is correct
20 Correct 1987 ms 12408 KB Output is correct
21 Correct 2092 ms 12924 KB Output is correct
22 Correct 1764 ms 13548 KB Output is correct
23 Correct 4694 ms 18960 KB Output is correct
24 Correct 4764 ms 19012 KB Output is correct
25 Correct 4382 ms 19064 KB Output is correct
26 Correct 4764 ms 23368 KB Output is correct
27 Incorrect 107 ms 18808 KB Output isn't correct
28 Halted 0 ms 0 KB -