oj.uz

답안 #94033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94033 2019-01-15T02:43:45 Z fjzzq2002 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
50 / 100
 2158 ms 158032 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[2255555];
vector<int> seq;
set<pii> ns;
int be[SZ],x[SZ],W;
vector<int> getseq()
{
	vector<int> v; v.reserve(n);
	for(auto t:seq)
		for(auto u:bl[t]) v.pb(u);
	return v;
}
#define j1 ju1
int j1[SZ];
pii js[SZ];
void reset_block(vector<int>&v)
{
	int j=0;
	for(int i=0;i<v.size();++i)
	{
		while(j<v.size()&&x[v[j]]<=x[v[i]]+W) ++j;
		if(j==v.size()) j1[v[i]]=-1;
		else j1[v[i]]=v[j];
	}
	for(int i=int(v.size())-1;i>=0;--i)
		if(j1[v[i]]==-1) js[v[i]]=pii(v[i],0);
		else js[v[i]]=pii(
		js[j1[v[i]]].fi,js[j1[v[i]]].se+1);
}
void rebuild(vector<int> v)
{
	int u=int(v.size())/B;
	if(!u) ++u;
	for(auto p:seq) bl[p].clear();
	seq.clear();
	vector<int> p;
	for(int i=0;i<int(v.size());++i)
	{
		p.pb(v[i]);
		if(p.size()>=u||i+1==int(v.size()))
			bl[++G]=p,reset_block(p),
			seq.pb(G),p.clear();
	}
}
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);
}
int update(int t,int y)
{
	ns.erase(pii(x[t],t));
	for(int i=0;i<int(seq.size());++i)
		if(x[t]<=x[bl[seq[i]].back()])
		{
			vector<int>&B=bl[seq[i]]; 
			B.erase(find(B.begin(),B.end(),t));
			if(B.size()) reset_block(B);
			else
			{
				seq.erase(seq.begin()+i);
				break;
			}
			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()))
		{
			vector<int> u,&s=bl[seq[i]];
			for(int j=0;j<s.size();++j)
				if(x[s[j]]<=x[t]) u.pb(s[j]);
			u.pb(t);
			for(int j=0;j<s.size();++j)
				if(x[s[j]]>x[t]) u.pb(s[j]);
			s=u; reset_block(s);
			break;
		}
//	for(auto t:seq)
//		for(auto g:bl[t])
//			cerr<<g<<",";cerr<<"\n";
	++cnt;
	if(cnt%B==0) rebuild(getseq());
	return ask();
}

Compilation message

elephants.cpp: In function 'void reset_block(std::vector<int>&)':
elephants.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();++i)
              ~^~~~~~~~~
elephants.cpp:31:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<v.size()&&x[v[j]]<=x[v[i]]+W) ++j;
         ~^~~~~~~~~
elephants.cpp:32:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j==v.size()) j1[v[i]]=-1;
      ~^~~~~~~~~~
elephants.cpp: In function 'void rebuild(std::vector<int>)':
elephants.cpp:50:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p.size()>=u||i+1==int(v.size()))
      ~~~~~~~~^~~
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:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 53368 KB Output is correct
2 Correct 50 ms 53368 KB Output is correct
3 Correct 49 ms 53460 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 53368 KB Output is correct
2 Correct 50 ms 53368 KB Output is correct
3 Correct 49 ms 53460 KB Output is correct
4 Correct 49 ms 53308 KB Output is correct
5 Correct 49 ms 53372 KB Output is correct
6 Correct 49 ms 53368 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 53368 KB Output is correct
2 Correct 50 ms 53368 KB Output is correct
3 Correct 49 ms 53460 KB Output is correct
4 Correct 49 ms 53308 KB Output is correct
5 Correct 49 ms 53372 KB Output is correct
6 Correct 49 ms 53368 KB Output is correct
7 Correct 609 ms 80464 KB Output is correct
8 Correct 711 ms 90728 KB Output is correct
9 Correct 1306 ms 156384 KB Output is correct
10 Correct 1330 ms 157516 KB Output is correct
11 Correct 1271 ms 157484 KB Output is correct
12 Correct 2158 ms 158032 KB Output is correct
13 Correct 2079 ms 157588 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 53368 KB Output is correct
2 Correct 50 ms 53368 KB Output is correct
3 Correct 49 ms 53460 KB Output is correct
4 Correct 49 ms 53308 KB Output is correct
5 Correct 49 ms 53372 KB Output is correct
6 Correct 49 ms 53368 KB Output is correct
7 Correct 609 ms 80464 KB Output is correct
8 Correct 711 ms 90728 KB Output is correct
9 Correct 1306 ms 156384 KB Output is correct
10 Correct 1330 ms 157516 KB Output is correct
11 Correct 1271 ms 157484 KB Output is correct
12 Correct 2158 ms 158032 KB Output is correct
13 Correct 2079 ms 157588 KB Output is correct
14 Runtime error 291 ms 135696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 53368 KB Output is correct
2 Correct 50 ms 53368 KB Output is correct
3 Correct 49 ms 53460 KB Output is correct
4 Correct 49 ms 53308 KB Output is correct
5 Correct 49 ms 53372 KB Output is correct
6 Correct 49 ms 53368 KB Output is correct
7 Correct 609 ms 80464 KB Output is correct
8 Correct 711 ms 90728 KB Output is correct
9 Correct 1306 ms 156384 KB Output is correct
10 Correct 1330 ms 157516 KB Output is correct
11 Correct 1271 ms 157484 KB Output is correct
12 Correct 2158 ms 158032 KB Output is correct
13 Correct 2079 ms 157588 KB Output is correct
14 Runtime error 291 ms 135696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -