oj.uz

Submission #94048

# Submission time Handle Problem Language Result Execution time Memory
94048 2019-01-15T03:50:25 Z fjzzq2002 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 21800 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ 305555
int n;
//B块
#define pb push_back
typedef pair<int,int> pii;
#define fi first
#define se second
int B=100,G=0;
vector<int> bl[SZ];
vector<int> seq;
int be[SZ],x[SZ],W,blk[SZ];
struct scmp
{
bool operator () (int a,int b)
{
	return (x[a]!=x[b])?(x[a]<x[b]):(a<b);
}
};
set<int,scmp> ns;
int ts[SZ];
int* getseq()
{
	int tn=0;
	for(auto t:seq)
		for(int j=0;j<bl[t].size();++j)
			ts[tn++]=bl[t][j];
	return ts;
}
#define j1 ju1
int j1[SZ];
pii js[SZ];
inline void reset_block(vector<int>&v_)
{
	int j=0,vn=v_.size(),*v=v_.data();
	for(int i=0;i<vn;++i)
	{
		while(j<vn&&x[v[j]]<=x[v[i]]+W) ++j;
		if(j==vn) j1[v[i]]=-1;
		else j1[v[i]]=v[j];
	}
	for(int i=int(vn)-1;i>=0;--i)
		if(j1[v[i]]==-1) js[v[i]].fi=v[i],js[v[i]].se=0;
		else
			js[v[i]].fi=js[j1[v[i]]].fi,
			js[v[i]].se=js[j1[v[i]]].se+1;
}
inline void rebuild(int*v)
{
	int u=int(n)/B;
	if(!u) ++u;
	for(int i=1;i<=G;++i) bl[i].clear();
	seq.clear(); G=0;
	vector<int> p; p.reserve(u);
	for(int i=0;i<n;++i)
	{
		p.pb(v[i]);
		if(p.size()>=u||i==n-1)
		{
			bl[++G]=p,reset_block(p);
			for(auto t:p) blk[t]=G;
			seq.pb(G),p.clear();
			p.reserve(u);
		}
	}
}
inline int ask()
{
	int s=*ns.begin(),cn=0;
	while(1)
	{
		if(js[s].se)
			cn+=js[s].se,s=js[s].fi;
		x[SZ-1]=x[s]+W;
		auto u=ns.lower_bound(SZ-1);
		++cn; if(u==ns.end()) break; s=*u;
	}
	return cn;
}
int cnt=0;
void init(int N, int L_, int X[])
{
	n=N; W=L_;
	for(int i=0;i<n;++i) x[i]=X[i];
	vector<int> v;
	for(int i=0;i<n;++i)
		v.pb(i),ns.insert(i);
	rebuild(v.data());
}
int update(int t,int y)
{
	ns.erase(t);
	{
		int i=blk[t];
		vector<int>&B=bl[i];
		for(int j=0;;++j)
			if(B[j]==t)
			{
				for(int k=j;k+1<B.size();++k)
					B[k]=B[k+1];
				B.pop_back(); break;
			}
		if(B.size()) reset_block(B);
		else
		{
			for(int j=0;;++j)
				if(seq[j]==i)
				{
					for(int k=j;k+1<seq.size();++k)
						seq[k]=seq[k+1];
					seq.pop_back(); break;
				}
		}
	}
	x[t]=y; ns.insert(t);
	for(int i=0;i<int(seq.size());++i)
		if(x[t]<=x[bl[seq[i]].back()]||i+1==int(seq.size()))
		{
			while(x[bl[seq[i]].back()]<=x[t]
			&&i+1!=int(seq.size())&&rand()%3) ++i;
			static int us[SZ]; int un=0;
			vector<int> &s=bl[seq[i]]; bool c=0;
			for(int j=0;j<s.size();++j)
			{
				if(x[s[j]]>x[t])
				{if(!c) us[un++]=t; c=1;}
				us[un++]=s[j];
			}
			if(!c) us[un++]=t; s.pb(0);
			for(int i=0;i<un;++i) s[i]=us[i];
			reset_block(s); blk[t]=seq[i];
			break;
		}
	++cnt;
	if(cnt%(B*4)==0) rebuild(getseq());
	return ask();
}

Compilation message

elephants.cpp: In function 'int* getseq()':
elephants.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<bl[t].size();++j)
               ~^~~~~~~~~~~~~
elephants.cpp: In function 'void rebuild(int*)':
elephants.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p.size()>=u||i==n-1)
      ~~~~~~~~^~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j;k+1<B.size();++k)
                 ~~~^~~~~~~~~
elephants.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=j;k+1<seq.size();++k)
                  ~~~^~~~~~~~~~~
elephants.cpp:125:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~
elephants.cpp:131:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(!c) us[un++]=t; s.pb(0);
    ^~
elephants.cpp:131:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    if(!c) us[un++]=t; s.pb(0);
                       ^

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7544 KB Output is correct
4 Correct 8 ms 7628 KB Output is correct
5 Correct 7 ms 7544 KB Output is correct
6 Correct 7 ms 7596 KB Output is correct
7 Correct 466 ms 9524 KB Output is correct
8 Correct 582 ms 9852 KB Output is correct
9 Correct 1113 ms 12428 KB Output is correct
10 Correct 1157 ms 12192 KB Output is correct
11 Correct 1082 ms 12196 KB Output is correct
12 Correct 2235 ms 12328 KB Output is correct
13 Correct 1847 ms 12196 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7544 KB Output is correct
4 Correct 8 ms 7628 KB Output is correct
5 Correct 7 ms 7544 KB Output is correct
6 Correct 7 ms 7596 KB Output is correct
7 Correct 466 ms 9524 KB Output is correct
8 Correct 582 ms 9852 KB Output is correct
9 Correct 1113 ms 12428 KB Output is correct
10 Correct 1157 ms 12192 KB Output is correct
11 Correct 1082 ms 12196 KB Output is correct
12 Correct 2235 ms 12328 KB Output is correct
13 Correct 1847 ms 12196 KB Output is correct
14 Correct 668 ms 9996 KB Output is correct
15 Correct 948 ms 10512 KB Output is correct
16 Correct 3314 ms 12580 KB Output is correct
17 Correct 4150 ms 14240 KB Output is correct
18 Correct 4217 ms 14288 KB Output is correct
19 Correct 2798 ms 14004 KB Output is correct
20 Correct 4021 ms 14288 KB Output is correct
21 Correct 3997 ms 14416 KB Output is correct
22 Correct 3183 ms 14032 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7544 KB Output is correct
4 Correct 8 ms 7628 KB Output is correct
5 Correct 7 ms 7544 KB Output is correct
6 Correct 7 ms 7596 KB Output is correct
7 Correct 466 ms 9524 KB Output is correct
8 Correct 582 ms 9852 KB Output is correct
9 Correct 1113 ms 12428 KB Output is correct
10 Correct 1157 ms 12192 KB Output is correct
11 Correct 1082 ms 12196 KB Output is correct
12 Correct 2235 ms 12328 KB Output is correct
13 Correct 1847 ms 12196 KB Output is correct
14 Correct 668 ms 9996 KB Output is correct
15 Correct 948 ms 10512 KB Output is correct
16 Correct 3314 ms 12580 KB Output is correct
17 Correct 4150 ms 14240 KB Output is correct
18 Correct 4217 ms 14288 KB Output is correct
19 Correct 2798 ms 14004 KB Output is correct
20 Correct 4021 ms 14288 KB Output is correct
21 Correct 3997 ms 14416 KB Output is correct
22 Correct 3183 ms 14032 KB Output is correct
23 Correct 8629 ms 21724 KB Output is correct
24 Execution timed out 9026 ms 21800 KB Time limit exceeded
25 Halted 0 ms 0 KB -