oj.uz

Submission #94054

# Submission time Handle Problem Language Result Execution time Memory
94054 2019-01-15T06:43:38 Z fjzzq2002 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 21884 KB 
#pragma GCC optimize("-Ofast","-funroll-all-loops","-fno-stack-protector")
#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=105,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];
		for(int j=0;;++j)
			if(B[j]==t) {B.erase(B.begin()+j); break;}
		if(B.size()) reset_block(B);
		else
		{
			for(int j=0;;++j)
				if(seq[j]==i) {seq.erase(seq.begin()+j); 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()))
		{
			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 '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:105:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~
elephants.cpp:111:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(!c) us[un++]=t; s.pb(0);
    ^~
elephants.cpp:111: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 9 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 9 ms 7544 KB Output is correct
3 Correct 7 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 9 ms 7544 KB Output is correct
3 Correct 7 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 454 ms 9652 KB Output is correct
8 Correct 506 ms 10004 KB Output is correct
9 Correct 1006 ms 12324 KB Output is correct
10 Correct 800 ms 12148 KB Output is correct
11 Correct 822 ms 12148 KB Output is correct
12 Correct 2057 ms 12412 KB Output is correct
13 Correct 1486 ms 12200 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 9 ms 7544 KB Output is correct
3 Correct 7 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 454 ms 9652 KB Output is correct
8 Correct 506 ms 10004 KB Output is correct
9 Correct 1006 ms 12324 KB Output is correct
10 Correct 800 ms 12148 KB Output is correct
11 Correct 822 ms 12148 KB Output is correct
12 Correct 2057 ms 12412 KB Output is correct
13 Correct 1486 ms 12200 KB Output is correct
14 Correct 635 ms 10020 KB Output is correct
15 Correct 902 ms 10356 KB Output is correct
16 Correct 3130 ms 12628 KB Output is correct
17 Correct 3751 ms 14284 KB Output is correct
18 Correct 3786 ms 14288 KB Output is correct
19 Correct 2348 ms 14028 KB Output is correct
20 Correct 3693 ms 14288 KB Output is correct
21 Correct 3379 ms 14388 KB Output is correct
22 Correct 2333 ms 13904 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 9 ms 7544 KB Output is correct
3 Correct 7 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 454 ms 9652 KB Output is correct
8 Correct 506 ms 10004 KB Output is correct
9 Correct 1006 ms 12324 KB Output is correct
10 Correct 800 ms 12148 KB Output is correct
11 Correct 822 ms 12148 KB Output is correct
12 Correct 2057 ms 12412 KB Output is correct
13 Correct 1486 ms 12200 KB Output is correct
14 Correct 635 ms 10020 KB Output is correct
15 Correct 902 ms 10356 KB Output is correct
16 Correct 3130 ms 12628 KB Output is correct
17 Correct 3751 ms 14284 KB Output is correct
18 Correct 3786 ms 14288 KB Output is correct
19 Correct 2348 ms 14028 KB Output is correct
20 Correct 3693 ms 14288 KB Output is correct
21 Correct 3379 ms 14388 KB Output is correct
22 Correct 2333 ms 13904 KB Output is correct
23 Correct 7684 ms 21656 KB Output is correct
24 Correct 8831 ms 21796 KB Output is correct
25 Correct 5839 ms 21560 KB Output is correct
26 Correct 5581 ms 21128 KB Output is correct
27 Correct 8262 ms 21220 KB Output is correct
28 Correct 1484 ms 9720 KB Output is correct
29 Correct 1315 ms 9848 KB Output is correct
30 Correct 1362 ms 9848 KB Output is correct
31 Correct 1304 ms 9848 KB Output is correct
32 Correct 5722 ms 21176 KB Output is correct
33 Correct 2704 ms 21264 KB Output is correct
34 Correct 4463 ms 21124 KB Output is correct
35 Correct 4170 ms 21884 KB Output is correct
36 Correct 4140 ms 21104 KB Output is correct
37 Execution timed out 9040 ms 21744 KB Time limit exceeded
38 Halted 0 ms 0 KB -