oj.uz

Submission #152657

# Submission time Handle Problem Language Result Execution time Memory
152657 2019-09-09T04:58:08 Z qkxwsm Dancing Elephants (IOI11_elephants) C++14
26 / 100
 22 ms 2424 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 150013
#define INF 1000000007
#define MAGIC 1700

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, L, Q, B;
int arr[MAXN];
set<int> vals;
vector<array<int, 3> > stor[MAGIC];
int ans;

//ok keep blocks of size k.
//each block stores: this guy takes x cost to jump to the end. and he arrives at y.
//ok so each query takes O(k) + O(N/k logN)
//so you choose k = sqrt(NlogN)
//so rebuild every sqrt(NlogN). each rebuild takes O(N).

void calc(int i)
{
	int iter = SZ(stor[i]) - 1;
	FORD(j, SZ(stor[i]), 0)
	{
		int x = stor[i][j][0];
		while(iter >= 0 && stor[i][iter][0] >= x + L) iter--;
		if (iter == SZ(stor[i]) - 1)
		{
			stor[i][j][1] = 1;
			stor[i][j][2] = x + L;
		}
		else
		{
			stor[i][j][1] = 1 + stor[i][iter + 1][1];
			stor[i][j][2] = stor[i][iter + 1][2];
		}
	}
}
void del(int v)
{
	//find which block has it.
	FORD(i, B, 0)
	{
		if (stor[i][0][0] > v) continue;
		//there's something that has x.
		FOR(j, 0, SZ(stor[i]))
		{
			if (stor[i][j][0] == v)
			{
				stor[i].erase(stor[i].begin() + j);
				break;
			}
		}
		calc(i);
		break;
	}
}
void ins(int v)
{
	FORD(i, B, 0)
	{
		if (stor[i][0][0] > v && i != 0) continue;
		FOR(j, 0, SZ(stor[i]) + 1)
		{
			if (j == SZ(stor[i]) || stor[i][j][0] > v)
			{
				stor[i].insert(stor[i].begin() + j, {v, 0, 0});
				break;
			}
		}
		calc(i);
	}
}
void build()
{
	FOR(i, 0, B)
	{
		stor[i].clear();
	}
	auto it = vals.begin();
	FOR(i, 0, B)
	{
		FOR(j, 0, MAGIC)
		{
			if (it == vals.end()) break;
			stor[i].PB({*it, 0, 0});
			it++;
		}
		calc(i);
	}
	return;
}
void debug()
{
	FOR(i, 0, B)
	{
		cerr << "BLOCK " << i << endl;
		FOR(j, 0, SZ(stor[i]))
		{
			FOR(k, 0, 3)
			{
				cerr << stor[i][j][k] << ' ';
			}
			cerr << endl;
		}
	}
}
int trav()
{
	int ans = 0, pos = -INF;
	FOR(i, 0, B)
	{
		//find the first guy that's > pos.
		array<int, 3> tmp = {pos, 0, 0};
		int idx = LB(ALL(stor[i]), tmp) - stor[i].begin();
		if (idx == SZ(stor[i])) continue;
		ans += stor[i][idx][1];
		pos = stor[i][idx][2];
	}
	return ans;
}
void init(int n, int l, int x[])
{
	N = n; L = l; B = (N + MAGIC - 1) / MAGIC;
	L++;
	FOR(i, 0, N)
	{
		arr[i] = x[i];
		vals.insert(arr[i]);
	}
	build();
}
int update(int idx, int v)
{
	vals.erase(arr[idx]);
	del(arr[idx]);
	arr[idx] = v;
	vals.insert(arr[idx]);
	ins(arr[idx]);
	Q++;
	if (Q % MAGIC == 0)
	{
		build();
	}
	// debug();
	ans = trav();
	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 372 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 372 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 22 ms 2424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 372 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 22 ms 2424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 372 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 22 ms 2424 KB Output isn't correct
8 Halted 0 ms 0 KB -