Submission #938806

#	Time	Username	Problem	Language	Result	Execution time	Memory
938806		pan	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	193 ms	22620 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
// general
ll range;
vector<ll> x;
// SQRT Data Structure
ll const blksz = 300;
ll blk;
vector<vector<ll> > groups;
vector<vector<pi> > dp;
ll query()
{
	//show(4);
	ll ret = 0;
	ll last = -1;
	for (ll i=0; i<blk; ++i)
	{
		if (groups[i].empty() || groups[i].back()<=last) continue;
		ll ind = ub(groups[i].begin(), groups[i].end(), last)-groups[i].begin();
		ret+=dp[i][ind].f;
		last = dp[i][ind].s;
	}
	return ret;
}
void processblk(ll ind)
{
	//show(3);
	if (groups[ind].empty()) return;
	ll n= groups[ind].size();
	dp[ind].clear();
	dp[ind].resize(n);
	ll r = n-1;
	for (ll l = n-1; l>=0; --l)
	{
		while (r-1>=l && groups[ind][r]-groups[ind][l]>range) {r--;}
		if (r==n-1) dp[ind][l] = mp(1, groups[ind][l] + range);
		else  dp[ind][l] = dp[ind][r+1], dp[ind][l].f++;
	}
}
void remove(ll pos)
{
	//show(1);
	ll i;
	for (i=0; i<blk; ++i)
	{
		if (groups[i].empty()) continue;
		if (groups[i][0]<=pos && groups[i].back()>=pos) break;
	}
	groups[i].erase(lb(groups[i].begin(), groups[i].end(), pos));
	processblk(i);
}
void insert(ll pos)
{
	//show(1);
	ll i;
	for (i=0; i<blk; ++i)
	{
		if (groups[i].empty()) continue;
		if (groups[i][0]>=pos) break;
	}
	if (i) i--;
	groups[i].insert(ub(groups[i].begin(), groups[i].end(), pos), pos);
	if (groups[i].size()>=2*blksz)
	{
		vector<ll> neww;
		ll half = groups[i].size()/2;
		while (half--) {neww.pb(groups[i].back()); groups[i].pop_back();}
		reverse(neww.begin(), neww.end());
		groups.insert(groups.begin()+i+1, neww);
		processblk(i);
		processblk(i+1);
		blk++;
	}
	else {processblk(i);}
}

void init(int N, int L, int X[])
{
	range = L;
	x.resize(N);
	blk = (N-1)/blksz + 1;
	groups.resize(blk);
	dp.resize(blk);
	for (ll i=0; i<N; ++i) groups[i/blksz].pb(X[i]);
	for (ll i=0; i<blk; ++i) processblk(i);
	for (ll i=0; i<N; ++i) x[i] = X[i];
}
int update(int i, int y)
{
	//show("FUCK");
	remove(x[i]);
	insert(y);
	x[i] = y;
	return query();
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3