oj.uz

Submission #94046

# Submission time Handle Problem Language Result Execution time Memory
94046 2019-01-15T03:41:00 Z fjzzq2002 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 21792 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;
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*4)==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 8 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 8 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 7544 KB Output is correct
6 Correct 8 ms 7544 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 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 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 443 ms 9492 KB Output is correct
8 Correct 499 ms 9764 KB Output is correct
9 Correct 951 ms 12456 KB Output is correct
10 Correct 955 ms 12120 KB Output is correct
11 Correct 1018 ms 12328 KB Output is correct
12 Correct 1670 ms 12324 KB Output is correct
13 Correct 1637 ms 12204 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 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 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 443 ms 9492 KB Output is correct
8 Correct 499 ms 9764 KB Output is correct
9 Correct 951 ms 12456 KB Output is correct
10 Correct 955 ms 12120 KB Output is correct
11 Correct 1018 ms 12328 KB Output is correct
12 Correct 1670 ms 12324 KB Output is correct
13 Correct 1637 ms 12204 KB Output is correct
14 Correct 494 ms 10016 KB Output is correct
15 Correct 814 ms 10400 KB Output is correct
16 Correct 2676 ms 12576 KB Output is correct
17 Correct 3259 ms 14416 KB Output is correct
18 Correct 3234 ms 14324 KB Output is correct
19 Correct 2280 ms 14032 KB Output is correct
20 Correct 3186 ms 14424 KB Output is correct
21 Correct 2981 ms 14160 KB Output is correct
22 Correct 2441 ms 13908 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 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 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 443 ms 9492 KB Output is correct
8 Correct 499 ms 9764 KB Output is correct
9 Correct 951 ms 12456 KB Output is correct
10 Correct 955 ms 12120 KB Output is correct
11 Correct 1018 ms 12328 KB Output is correct
12 Correct 1670 ms 12324 KB Output is correct
13 Correct 1637 ms 12204 KB Output is correct
14 Correct 494 ms 10016 KB Output is correct
15 Correct 814 ms 10400 KB Output is correct
16 Correct 2676 ms 12576 KB Output is correct
17 Correct 3259 ms 14416 KB Output is correct
18 Correct 3234 ms 14324 KB Output is correct
19 Correct 2280 ms 14032 KB Output is correct
20 Correct 3186 ms 14424 KB Output is correct
21 Correct 2981 ms 14160 KB Output is correct
22 Correct 2441 ms 13908 KB Output is correct
23 Correct 7332 ms 21792 KB Output is correct
24 Correct 8160 ms 21792 KB Output is correct
25 Correct 5642 ms 21656 KB Output is correct
26 Correct 7712 ms 21236 KB Output is correct
27 Correct 6862 ms 21232 KB Output is correct
28 Correct 785 ms 9820 KB Output is correct
29 Correct 764 ms 9728 KB Output is correct
30 Correct 863 ms 9780 KB Output is correct
31 Correct 728 ms 9848 KB Output is correct
32 Correct 7188 ms 21160 KB Output is correct
33 Correct 4325 ms 21144 KB Output is correct
34 Correct 5862 ms 21140 KB Output is correct
35 Correct 4632 ms 21704 KB Output is correct
36 Correct 4760 ms 21472 KB Output is correct
37 Execution timed out 9034 ms 21672 KB Time limit exceeded
38 Halted 0 ms 0 KB -