oj.uz

답안 #94041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94041 2019-01-15T03:26:53 Z fjzzq2002 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
26 / 100
 182 ms 18316 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 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7544 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7544 KB Output is correct
4 Correct 9 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
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7544 KB Output is correct
4 Correct 9 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 Runtime error 182 ms 18316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7544 KB Output is correct
4 Correct 9 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 Runtime error 182 ms 18316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 7 ms 7544 KB Output is correct
4 Correct 9 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 Runtime error 182 ms 18316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -