oj.uz

Submission #94937

# Submission time Handle Problem Language Result Execution time Memory
94937 2019-01-25T10:51:52 Z MvC Dancing Elephants (IOI11_elephants) C++11
100 / 100
 7547 ms 33228 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++;
	s.er(s.fd(x[i]));
	del(x[i]);
	x[i]=y;
  	s.in(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:120: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 14456 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 14456 KB Output is correct
4 Correct 13 ms 14456 KB Output is correct
5 Correct 13 ms 14428 KB Output is correct
6 Correct 15 ms 14456 KB Output is correct

Subtask #3
24.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 14456 KB Output is correct
4 Correct 13 ms 14456 KB Output is correct
5 Correct 13 ms 14428 KB Output is correct
6 Correct 15 ms 14456 KB Output is correct
7 Correct 520 ms 16304 KB Output is correct
8 Correct 559 ms 17528 KB Output is correct
9 Correct 667 ms 20192 KB Output is correct
10 Correct 496 ms 19884 KB Output is correct
11 Correct 498 ms 19704 KB Output is correct
12 Correct 952 ms 20264 KB Output is correct
13 Correct 489 ms 19576 KB Output is correct

Subtask #4
47.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 14456 KB Output is correct
4 Correct 13 ms 14456 KB Output is correct
5 Correct 13 ms 14428 KB Output is correct
6 Correct 15 ms 14456 KB Output is correct
7 Correct 520 ms 16304 KB Output is correct
8 Correct 559 ms 17528 KB Output is correct
9 Correct 667 ms 20192 KB Output is correct
10 Correct 496 ms 19884 KB Output is correct
11 Correct 498 ms 19704 KB Output is correct
12 Correct 952 ms 20264 KB Output is correct
13 Correct 489 ms 19576 KB Output is correct
14 Correct 662 ms 18224 KB Output is correct
15 Correct 766 ms 18532 KB Output is correct
16 Correct 1489 ms 20900 KB Output is correct
17 Correct 1697 ms 22652 KB Output is correct
18 Correct 1826 ms 22656 KB Output is correct
19 Correct 1175 ms 22160 KB Output is correct
20 Correct 1691 ms 22712 KB Output is correct
21 Correct 1575 ms 22492 KB Output is correct
22 Correct 968 ms 21624 KB Output is correct

Subtask #5
3.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 14456 KB Output is correct
4 Correct 13 ms 14456 KB Output is correct
5 Correct 13 ms 14428 KB Output is correct
6 Correct 15 ms 14456 KB Output is correct
7 Correct 520 ms 16304 KB Output is correct
8 Correct 559 ms 17528 KB Output is correct
9 Correct 667 ms 20192 KB Output is correct
10 Correct 496 ms 19884 KB Output is correct
11 Correct 498 ms 19704 KB Output is correct
12 Correct 952 ms 20264 KB Output is correct
13 Correct 489 ms 19576 KB Output is correct
14 Correct 662 ms 18224 KB Output is correct
15 Correct 766 ms 18532 KB Output is correct
16 Correct 1489 ms 20900 KB Output is correct
17 Correct 1697 ms 22652 KB Output is correct
18 Correct 1826 ms 22656 KB Output is correct
19 Correct 1175 ms 22160 KB Output is correct
20 Correct 1691 ms 22712 KB Output is correct
21 Correct 1575 ms 22492 KB Output is correct
22 Correct 968 ms 21624 KB Output is correct
23 Correct 4906 ms 32240 KB Output is correct
24 Correct 5000 ms 32188 KB Output is correct
25 Correct 4035 ms 31988 KB Output is correct
26 Correct 3686 ms 31316 KB Output is correct
27 Correct 4066 ms 31140 KB Output is correct
28 Correct 2053 ms 19548 KB Output is correct
29 Correct 1987 ms 19576 KB Output is correct
30 Correct 2029 ms 19516 KB Output is correct
31 Correct 1991 ms 19632 KB Output is correct
32 Correct 3598 ms 30712 KB Output is correct
33 Correct 3296 ms 30072 KB Output is correct
34 Correct 3907 ms 30920 KB Output is correct
35 Correct 3694 ms 33228 KB Output is correct
36 Correct 3855 ms 30696 KB Output is correct
37 Correct 6668 ms 32792 KB Output is correct
38 Correct 3992 ms 29968 KB Output is correct
39 Correct 3826 ms 31068 KB Output is correct
40 Correct 3494 ms 30072 KB Output is correct
41 Correct 7547 ms 32048 KB Output is correct
42 Correct 6273 ms 32248 KB Output is correct