oj.uz

Submission #94049

# Submission time Handle Problem Language Result Execution time Memory
94049 2019-01-15T04:00:19 Z fjzzq2002 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 21900 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=150,G=0;
vector<int> bl[SZ];
vector<int> seq;
set<pii> ns;
int be[SZ],x[SZ],W,blk[SZ];
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()->se,cn=0;
	while(1)
	{
		if(js[s].se)
			cn+=js[s].se,s=js[s].fi;
		auto u=ns.lower_bound(pii(x[s]+W+1,0));
		++cn; if(u==ns.end()) break; s=u->se;
	}
	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(pii(x[i],i));
	rebuild(v.data());
}
int update(int t,int y)
{
	ns.erase(pii(x[t],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(pii(x[t],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*3)==0) rebuild(getseq());
	return ask();
}

Compilation message

elephants.cpp: In function 'int* getseq()':
elephants.cpp:21: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:53: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:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j;k+1<B.size();++k)
                 ~~~^~~~~~~~~
elephants.cpp:103:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=j;k+1<seq.size();++k)
                  ~~~^~~~~~~~~~~
elephants.cpp:117:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~
elephants.cpp:123:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(!c) us[un++]=t; s.pb(0);
    ^~
elephants.cpp:123: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 7 ms 7544 KB Output is correct
2 Correct 7 ms 7544 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7544 KB Output is correct
2 Correct 7 ms 7544 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 8 ms 7544 KB Output is correct
5 Correct 8 ms 7548 KB Output is correct
6 Correct 7 ms 7544 KB Output is correct
7 Correct 714 ms 9504 KB Output is correct
8 Correct 804 ms 9836 KB Output is correct
9 Correct 1373 ms 12288 KB Output is correct
10 Correct 1337 ms 12148 KB Output is correct
11 Correct 933 ms 12112 KB Output is correct
12 Correct 2218 ms 12452 KB Output is correct
13 Correct 2035 ms 12116 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7544 KB Output is correct
2 Correct 7 ms 7544 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 8 ms 7544 KB Output is correct
5 Correct 8 ms 7548 KB Output is correct
6 Correct 7 ms 7544 KB Output is correct
7 Correct 714 ms 9504 KB Output is correct
8 Correct 804 ms 9836 KB Output is correct
9 Correct 1373 ms 12288 KB Output is correct
10 Correct 1337 ms 12148 KB Output is correct
11 Correct 933 ms 12112 KB Output is correct
12 Correct 2218 ms 12452 KB Output is correct
13 Correct 2035 ms 12116 KB Output is correct
14 Correct 723 ms 9892 KB Output is correct
15 Correct 1282 ms 10388 KB Output is correct
16 Correct 3240 ms 12568 KB Output is correct
17 Correct 4049 ms 14156 KB Output is correct
18 Correct 4232 ms 14272 KB Output is correct
19 Correct 2976 ms 13912 KB Output is correct
20 Correct 3995 ms 14228 KB Output is correct
21 Correct 4074 ms 14284 KB Output is correct
22 Correct 3228 ms 13912 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7544 KB Output is correct
2 Correct 7 ms 7544 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 8 ms 7544 KB Output is correct
5 Correct 8 ms 7548 KB Output is correct
6 Correct 7 ms 7544 KB Output is correct
7 Correct 714 ms 9504 KB Output is correct
8 Correct 804 ms 9836 KB Output is correct
9 Correct 1373 ms 12288 KB Output is correct
10 Correct 1337 ms 12148 KB Output is correct
11 Correct 933 ms 12112 KB Output is correct
12 Correct 2218 ms 12452 KB Output is correct
13 Correct 2035 ms 12116 KB Output is correct
14 Correct 723 ms 9892 KB Output is correct
15 Correct 1282 ms 10388 KB Output is correct
16 Correct 3240 ms 12568 KB Output is correct
17 Correct 4049 ms 14156 KB Output is correct
18 Correct 4232 ms 14272 KB Output is correct
19 Correct 2976 ms 13912 KB Output is correct
20 Correct 3995 ms 14228 KB Output is correct
21 Correct 4074 ms 14284 KB Output is correct
22 Correct 3228 ms 13912 KB Output is correct
23 Correct 8010 ms 21900 KB Output is correct
24 Execution timed out 9025 ms 21792 KB Time limit exceeded
25 Halted 0 ms 0 KB -