oj.uz

Submission #94043

# Submission time Handle Problem Language Result Execution time Memory
94043 2019-01-15T03:32:21 Z fjzzq2002 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 26784 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(auto u:bl[t]) ts[tn++]=u;
	return ts;
}
#define j1 ju1
int j1[SZ];
pii js[SZ];
inline void reset_block(vector<int>&v)
{
	int j=0,vn=v.size();
	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];
		B.erase(find(B.begin(),B.end(),t));
		if(B.size()) reset_block(B);
		else seq.erase(find(seq.begin(),seq.end(),i));
	}
	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()))
		{
			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+B+B)==0) rebuild(getseq());
	return ask();
}

Compilation message

elephants.cpp: In function 'void rebuild(int*)':
elephants.cpp:52: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:99:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~
elephants.cpp:105:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(!c) us[un++]=t; s.pb(0);
    ^~
elephants.cpp:105: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 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 8 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 7 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 8 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 7 ms 7544 KB Output is correct
7 Correct 440 ms 9464 KB Output is correct
8 Correct 490 ms 9916 KB Output is correct
9 Correct 936 ms 12324 KB Output is correct
10 Correct 967 ms 12196 KB Output is correct
11 Correct 1072 ms 12196 KB Output is correct
12 Correct 1821 ms 12328 KB Output is correct
13 Correct 1617 ms 12192 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 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 7 ms 7544 KB Output is correct
7 Correct 440 ms 9464 KB Output is correct
8 Correct 490 ms 9916 KB Output is correct
9 Correct 936 ms 12324 KB Output is correct
10 Correct 967 ms 12196 KB Output is correct
11 Correct 1072 ms 12196 KB Output is correct
12 Correct 1821 ms 12328 KB Output is correct
13 Correct 1617 ms 12192 KB Output is correct
14 Correct 607 ms 10020 KB Output is correct
15 Correct 801 ms 10384 KB Output is correct
16 Correct 2894 ms 12584 KB Output is correct
17 Correct 3768 ms 14284 KB Output is correct
18 Correct 3878 ms 14264 KB Output is correct
19 Correct 2373 ms 14028 KB Output is correct
20 Correct 3482 ms 14216 KB Output is correct
21 Correct 3428 ms 14252 KB Output is correct
22 Correct 2606 ms 13900 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 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 7 ms 7544 KB Output is correct
7 Correct 440 ms 9464 KB Output is correct
8 Correct 490 ms 9916 KB Output is correct
9 Correct 936 ms 12324 KB Output is correct
10 Correct 967 ms 12196 KB Output is correct
11 Correct 1072 ms 12196 KB Output is correct
12 Correct 1821 ms 12328 KB Output is correct
13 Correct 1617 ms 12192 KB Output is correct
14 Correct 607 ms 10020 KB Output is correct
15 Correct 801 ms 10384 KB Output is correct
16 Correct 2894 ms 12584 KB Output is correct
17 Correct 3768 ms 14284 KB Output is correct
18 Correct 3878 ms 14264 KB Output is correct
19 Correct 2373 ms 14028 KB Output is correct
20 Correct 3482 ms 14216 KB Output is correct
21 Correct 3428 ms 14252 KB Output is correct
22 Correct 2606 ms 13900 KB Output is correct
23 Correct 7412 ms 21736 KB Output is correct
24 Correct 8576 ms 21916 KB Output is correct
25 Correct 5943 ms 26784 KB Output is correct
26 Execution timed out 9085 ms 26128 KB Time limit exceeded
27 Halted 0 ms 0 KB -