oj.uz

답안 #94042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94042 2019-01-15T03:31:15 Z fjzzq2002 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
97 / 100
 9000 ms 21720 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==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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 7 ms 7516 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 7 ms 7516 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 478 ms 9272 KB Output is correct
8 Correct 566 ms 9652 KB Output is correct
9 Correct 1112 ms 12320 KB Output is correct
10 Correct 1283 ms 12116 KB Output is correct
11 Correct 1070 ms 12192 KB Output is correct
12 Correct 2202 ms 12516 KB Output is correct
13 Correct 2109 ms 12192 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 7 ms 7516 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 478 ms 9272 KB Output is correct
8 Correct 566 ms 9652 KB Output is correct
9 Correct 1112 ms 12320 KB Output is correct
10 Correct 1283 ms 12116 KB Output is correct
11 Correct 1070 ms 12192 KB Output is correct
12 Correct 2202 ms 12516 KB Output is correct
13 Correct 2109 ms 12192 KB Output is correct
14 Correct 704 ms 9988 KB Output is correct
15 Correct 1022 ms 10496 KB Output is correct
16 Correct 3667 ms 12680 KB Output is correct
17 Correct 4500 ms 14288 KB Output is correct
18 Correct 4674 ms 14360 KB Output is correct
19 Correct 2734 ms 14032 KB Output is correct
20 Correct 4445 ms 14284 KB Output is correct
21 Correct 4296 ms 14300 KB Output is correct
22 Correct 3324 ms 14004 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 7 ms 7516 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 478 ms 9272 KB Output is correct
8 Correct 566 ms 9652 KB Output is correct
9 Correct 1112 ms 12320 KB Output is correct
10 Correct 1283 ms 12116 KB Output is correct
11 Correct 1070 ms 12192 KB Output is correct
12 Correct 2202 ms 12516 KB Output is correct
13 Correct 2109 ms 12192 KB Output is correct
14 Correct 704 ms 9988 KB Output is correct
15 Correct 1022 ms 10496 KB Output is correct
16 Correct 3667 ms 12680 KB Output is correct
17 Correct 4500 ms 14288 KB Output is correct
18 Correct 4674 ms 14360 KB Output is correct
19 Correct 2734 ms 14032 KB Output is correct
20 Correct 4445 ms 14284 KB Output is correct
21 Correct 4296 ms 14300 KB Output is correct
22 Correct 3324 ms 14004 KB Output is correct
23 Execution timed out 9014 ms 21720 KB Time limit exceeded
24 Halted 0 ms 0 KB -