oj.uz

Submission #94031

# Submission time Handle Problem Language Result Execution time Memory
94031 2019-01-15T02:34:09 Z fjzzq2002 Dancing Elephants (IOI11_elephants) C++14
26 / 100
 41 ms 32504 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[1255555];
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));
	int ps=seq.size();
	for(int i=0;i<int(seq.size());++i)
		if(x[t]<=x[bl[seq[i]].front()]) {ps=i; break;}
	bl[++G]={t};
	seq.insert(seq.begin()+ps,G);
	++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()))
      ~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 29944 KB Output is correct
2 Correct 23 ms 29816 KB Output is correct
3 Correct 24 ms 29816 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 29944 KB Output is correct
2 Correct 23 ms 29816 KB Output is correct
3 Correct 24 ms 29816 KB Output is correct
4 Correct 24 ms 29944 KB Output is correct
5 Correct 24 ms 30072 KB Output is correct
6 Correct 23 ms 29816 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 29944 KB Output is correct
2 Correct 23 ms 29816 KB Output is correct
3 Correct 24 ms 29816 KB Output is correct
4 Correct 24 ms 29944 KB Output is correct
5 Correct 24 ms 30072 KB Output is correct
6 Correct 23 ms 29816 KB Output is correct
7 Incorrect 41 ms 32504 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 29944 KB Output is correct
2 Correct 23 ms 29816 KB Output is correct
3 Correct 24 ms 29816 KB Output is correct
4 Correct 24 ms 29944 KB Output is correct
5 Correct 24 ms 30072 KB Output is correct
6 Correct 23 ms 29816 KB Output is correct
7 Incorrect 41 ms 32504 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 29944 KB Output is correct
2 Correct 23 ms 29816 KB Output is correct
3 Correct 24 ms 29816 KB Output is correct
4 Correct 24 ms 29944 KB Output is correct
5 Correct 24 ms 30072 KB Output is correct
6 Correct 23 ms 29816 KB Output is correct
7 Incorrect 41 ms 32504 KB Output isn't correct
8 Halted 0 ms 0 KB -