oj.uz

Submission #94044

# Submission time Handle Problem Language Result Execution time Memory
94044 2019-01-15T03:34:58 Z fjzzq2002 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 26768 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];
		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: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:104:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~
elephants.cpp:110:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(!c) us[un++]=t; s.pb(0);
    ^~
elephants.cpp:110: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 7 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 7 ms 7544 KB Output is correct
4 Correct 7 ms 7544 KB Output is correct
5 Correct 7 ms 7588 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 7 ms 7544 KB Output is correct
4 Correct 7 ms 7544 KB Output is correct
5 Correct 7 ms 7588 KB Output is correct
6 Correct 7 ms 7544 KB Output is correct
7 Correct 432 ms 9376 KB Output is correct
8 Correct 494 ms 9748 KB Output is correct
9 Correct 911 ms 12324 KB Output is correct
10 Correct 918 ms 12168 KB Output is correct
11 Correct 943 ms 12172 KB Output is correct
12 Correct 1829 ms 12324 KB Output is correct
13 Correct 1566 ms 12192 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 7 ms 7544 KB Output is correct
4 Correct 7 ms 7544 KB Output is correct
5 Correct 7 ms 7588 KB Output is correct
6 Correct 7 ms 7544 KB Output is correct
7 Correct 432 ms 9376 KB Output is correct
8 Correct 494 ms 9748 KB Output is correct
9 Correct 911 ms 12324 KB Output is correct
10 Correct 918 ms 12168 KB Output is correct
11 Correct 943 ms 12172 KB Output is correct
12 Correct 1829 ms 12324 KB Output is correct
13 Correct 1566 ms 12192 KB Output is correct
14 Correct 606 ms 10048 KB Output is correct
15 Correct 815 ms 10516 KB Output is correct
16 Correct 2947 ms 12676 KB Output is correct
17 Correct 3544 ms 14288 KB Output is correct
18 Correct 3791 ms 14300 KB Output is correct
19 Correct 2412 ms 13956 KB Output is correct
20 Correct 3523 ms 14288 KB Output is correct
21 Correct 3508 ms 14328 KB Output is correct
22 Correct 2716 ms 14032 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 7 ms 7544 KB Output is correct
4 Correct 7 ms 7544 KB Output is correct
5 Correct 7 ms 7588 KB Output is correct
6 Correct 7 ms 7544 KB Output is correct
7 Correct 432 ms 9376 KB Output is correct
8 Correct 494 ms 9748 KB Output is correct
9 Correct 911 ms 12324 KB Output is correct
10 Correct 918 ms 12168 KB Output is correct
11 Correct 943 ms 12172 KB Output is correct
12 Correct 1829 ms 12324 KB Output is correct
13 Correct 1566 ms 12192 KB Output is correct
14 Correct 606 ms 10048 KB Output is correct
15 Correct 815 ms 10516 KB Output is correct
16 Correct 2947 ms 12676 KB Output is correct
17 Correct 3544 ms 14288 KB Output is correct
18 Correct 3791 ms 14300 KB Output is correct
19 Correct 2412 ms 13956 KB Output is correct
20 Correct 3523 ms 14288 KB Output is correct
21 Correct 3508 ms 14328 KB Output is correct
22 Correct 2716 ms 14032 KB Output is correct
23 Correct 7163 ms 21620 KB Output is correct
24 Correct 8786 ms 21776 KB Output is correct
25 Correct 5772 ms 21580 KB Output is correct
26 Correct 7612 ms 21196 KB Output is correct
27 Correct 6997 ms 26028 KB Output is correct
28 Correct 1447 ms 12792 KB Output is correct
29 Correct 1185 ms 12676 KB Output is correct
30 Correct 1455 ms 12712 KB Output is correct
31 Correct 1286 ms 12664 KB Output is correct
32 Correct 6806 ms 25616 KB Output is correct
33 Correct 4218 ms 24976 KB Output is correct
34 Correct 5856 ms 26028 KB Output is correct
35 Correct 4339 ms 26768 KB Output is correct
36 Correct 4548 ms 25580 KB Output is correct
37 Execution timed out 9011 ms 26636 KB Time limit exceeded
38 Halted 0 ms 0 KB -