oj.uz

Submission #94037

# Submission time Handle Problem Language Result Execution time Memory
94037 2019-01-15T03:14:14 Z fjzzq2002 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 21648 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=50,G=0;
vector<int> bl[SZ];
vector<int> seq;
set<pii> ns;
int be[SZ],x[SZ],W,blk[SZ];
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(int i=1;i<=G;++i) bl[i].clear();
	seq.clear(); G=0;
	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);
			for(auto t:p) blk[t]=G;
			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));
	{
		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()))
		{
			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); blk[t]=seq[i];
			break;
		}
	++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:96:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~
elephants.cpp:99: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

# Verdict Execution time Memory Grader output
1 Correct 8 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

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 7544 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7576 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 7544 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7576 KB Output is correct
7 Correct 583 ms 9208 KB Output is correct
8 Correct 751 ms 9616 KB Output is correct
9 Correct 1484 ms 12276 KB Output is correct
10 Correct 1520 ms 12272 KB Output is correct
11 Correct 1512 ms 12276 KB Output is correct
12 Correct 3084 ms 12276 KB Output is correct
13 Correct 1769 ms 12276 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 7544 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7576 KB Output is correct
7 Correct 583 ms 9208 KB Output is correct
8 Correct 751 ms 9616 KB Output is correct
9 Correct 1484 ms 12276 KB Output is correct
10 Correct 1520 ms 12272 KB Output is correct
11 Correct 1512 ms 12276 KB Output is correct
12 Correct 3084 ms 12276 KB Output is correct
13 Correct 1769 ms 12276 KB Output is correct
14 Correct 900 ms 9888 KB Output is correct
15 Correct 1313 ms 10516 KB Output is correct
16 Correct 5211 ms 12532 KB Output is correct
17 Correct 6834 ms 14188 KB Output is correct
18 Correct 7093 ms 14268 KB Output is correct
19 Correct 3103 ms 14192 KB Output is correct
20 Correct 6517 ms 14192 KB Output is correct
21 Correct 6056 ms 14200 KB Output is correct
22 Correct 3340 ms 14192 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 7544 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7576 KB Output is correct
7 Correct 583 ms 9208 KB Output is correct
8 Correct 751 ms 9616 KB Output is correct
9 Correct 1484 ms 12276 KB Output is correct
10 Correct 1520 ms 12272 KB Output is correct
11 Correct 1512 ms 12276 KB Output is correct
12 Correct 3084 ms 12276 KB Output is correct
13 Correct 1769 ms 12276 KB Output is correct
14 Correct 900 ms 9888 KB Output is correct
15 Correct 1313 ms 10516 KB Output is correct
16 Correct 5211 ms 12532 KB Output is correct
17 Correct 6834 ms 14188 KB Output is correct
18 Correct 7093 ms 14268 KB Output is correct
19 Correct 3103 ms 14192 KB Output is correct
20 Correct 6517 ms 14192 KB Output is correct
21 Correct 6056 ms 14200 KB Output is correct
22 Correct 3340 ms 14192 KB Output is correct
23 Execution timed out 9071 ms 21648 KB Time limit exceeded
24 Halted 0 ms 0 KB -