oj.uz

Submission #94936

# Submission time Handle Problem Language Result Execution time Memory
94936 2019-01-25T10:48:26 Z MvC Dancing Elephants (IOI11_elephants) C++11
26 / 100
 34 ms 16856 KB 
#include "elephants.h"
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const int mod=1e9+7;
const int sq=500;
using namespace std;
int n,l,x[nmax],nr,step;
vector<int>v[nmax],ad[nmax],nx[nmax];
multiset<int>s;
multiset<int>::iterator it;
void bld(int b)
{
	int m=v[b].size();
	int j=m;
	nx[b].resize(m);
	ad[b].resize(m);
	for(int i=m-1;i>=0;i--)
	{
		while(v[b][i]+l<v[b][j-1])j--;
		ad[b][i]=1;
		nx[b][i]=v[b][i];
		if(j<m)
		{
			ad[b][i]+=ad[b][j];
			nx[b][i]=nx[b][j];
		}
	}
}
void build()
{
	nr=(n+sq-1)/sq;
	int j=0;
	for(int i=0;i<nr;i++)v[i].clear(),nx[i].clear(),ad[i].clear();
	for(it=s.begin();it!=s.end();it++)
	{
		v[j/sq].pb((*it));
		j++;
	}
	for(int i=0;i<nr;i++)bld(i);
}
void init(int N,int L,int X[])
{
	n=N,l=L;
	for(int i=0;i<n;i++)
	{
		x[i]=X[i];
		s.in(x[i]);
	}
}
void del(int y)
{
	for(int i=0;i<nr;i++)
	{
		if(!v[i].empty() && v[i][0]<=y && y<=v[i].back())
		{
			vector<int>nv;
			for(int j=0;j<v[i].size();j++)
			{
				if(y!=v[i][j])nv.pb(v[i][j]);
				else y=inf;
			}
			v[i]=nv;
			bld(i);
			break;
		}
	}
}
void add(int y)
{
	int i;
	for(i=0;i<nr;i++)
	{
		if(!v[i].empty() && y<=v[i].back())
		{
			vector<int>nv;
			for(int j=0;j<v[i].size();j++)
			{
				if(v[i][j]>y)nv.pb(y),y=inf;
				nv.pb(v[i][j]);
			}
			if(y!=inf)nv.pb(y);
			v[i]=nv;
			bld(i);
			break;
		}
	}
	if(i==nr)
	{
		v[nr-1].pb(y);
		bld(nr-1);
	}
}
int update(int i,int y)
{
	if(step%sq==0)build();
	step++;
	del(x[i]);
	x[i]=y;
	add(x[i]);
	int pre=-inf;
	int ans=0;
	for(int i=0;i<nr;i++)
	{
		int lo=lower_bound(v[i].begin(),v[i].end(),pre)-v[i].begin();
		if(lo!=v[i].size())
		{
			pre=nx[i][lo]+l+1;
			ans+=ad[i][lo];
		}
	}
	return ans;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	
	return 0;
}*/

Compilation message

elephants.cpp: In function 'void del(int)':
elephants.cpp:70:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<v[i].size();j++)
                ~^~~~~~~~~~~~
elephants.cpp: In function 'void add(int)':
elephants.cpp:89:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<v[i].size();j++)
                ~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:118:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(lo!=v[i].size())
      ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 13 ms 14456 KB Output is correct
3 Correct 13 ms 14428 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 13 ms 14456 KB Output is correct
3 Correct 13 ms 14428 KB Output is correct
4 Correct 11 ms 14456 KB Output is correct
5 Correct 13 ms 14456 KB Output is correct
6 Correct 13 ms 14456 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 13 ms 14456 KB Output is correct
3 Correct 13 ms 14428 KB Output is correct
4 Correct 11 ms 14456 KB Output is correct
5 Correct 13 ms 14456 KB Output is correct
6 Correct 13 ms 14456 KB Output is correct
7 Incorrect 34 ms 16856 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 13 ms 14456 KB Output is correct
3 Correct 13 ms 14428 KB Output is correct
4 Correct 11 ms 14456 KB Output is correct
5 Correct 13 ms 14456 KB Output is correct
6 Correct 13 ms 14456 KB Output is correct
7 Incorrect 34 ms 16856 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 13 ms 14456 KB Output is correct
3 Correct 13 ms 14428 KB Output is correct
4 Correct 11 ms 14456 KB Output is correct
5 Correct 13 ms 14456 KB Output is correct
6 Correct 13 ms 14456 KB Output is correct
7 Incorrect 34 ms 16856 KB Output isn't correct
8 Halted 0 ms 0 KB -