oj.uz

답안 #94032

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94032 2019-01-15T02:42:39 Z fjzzq2002 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
50 / 100
 2119 ms 159456 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;
	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:49: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:98:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~
elephants.cpp:101: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 42 ms 53368 KB Output is correct
2 Correct 41 ms 53376 KB Output is correct
3 Correct 43 ms 53368 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 53368 KB Output is correct
2 Correct 41 ms 53376 KB Output is correct
3 Correct 43 ms 53368 KB Output is correct
4 Correct 42 ms 53368 KB Output is correct
5 Correct 44 ms 53368 KB Output is correct
6 Correct 51 ms 53304 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 53368 KB Output is correct
2 Correct 41 ms 53376 KB Output is correct
3 Correct 43 ms 53368 KB Output is correct
4 Correct 42 ms 53368 KB Output is correct
5 Correct 44 ms 53368 KB Output is correct
6 Correct 51 ms 53304 KB Output is correct
7 Correct 585 ms 80152 KB Output is correct
8 Correct 707 ms 91684 KB Output is correct
9 Correct 1279 ms 157904 KB Output is correct
10 Correct 1351 ms 158952 KB Output is correct
11 Correct 1380 ms 158808 KB Output is correct
12 Correct 2119 ms 159456 KB Output is correct
13 Correct 2077 ms 158684 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 53368 KB Output is correct
2 Correct 41 ms 53376 KB Output is correct
3 Correct 43 ms 53368 KB Output is correct
4 Correct 42 ms 53368 KB Output is correct
5 Correct 44 ms 53368 KB Output is correct
6 Correct 51 ms 53304 KB Output is correct
7 Correct 585 ms 80152 KB Output is correct
8 Correct 707 ms 91684 KB Output is correct
9 Correct 1279 ms 157904 KB Output is correct
10 Correct 1351 ms 158952 KB Output is correct
11 Correct 1380 ms 158808 KB Output is correct
12 Correct 2119 ms 159456 KB Output is correct
13 Correct 2077 ms 158684 KB Output is correct
14 Runtime error 296 ms 137344 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 42 ms 53368 KB Output is correct
2 Correct 41 ms 53376 KB Output is correct
3 Correct 43 ms 53368 KB Output is correct
4 Correct 42 ms 53368 KB Output is correct
5 Correct 44 ms 53368 KB Output is correct
6 Correct 51 ms 53304 KB Output is correct
7 Correct 585 ms 80152 KB Output is correct
8 Correct 707 ms 91684 KB Output is correct
9 Correct 1279 ms 157904 KB Output is correct
10 Correct 1351 ms 158952 KB Output is correct
11 Correct 1380 ms 158808 KB Output is correct
12 Correct 2119 ms 159456 KB Output is correct
13 Correct 2077 ms 158684 KB Output is correct
14 Runtime error 296 ms 137344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -