oj.uz

Submission #152659

# Submission time Handle Problem Language Result Execution time Memory
152659 2019-09-09T05:38:33 Z qkxwsm Dancing Elephants (IOI11_elephants) C++14
50 / 100
 1669 ms 6028 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). solution in Nsqrt(NlogN)

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);
		break;
	}
}
void build()
{
	auto it = vals.begin();
	FOR(i, 0, B)
	{
		stor[i].clear();
		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 res = 0, pos = -INF;
	FOR(i, 0, B)
	{
		//find the first guy that's > pos.
		array<int, 3> tmp = {pos, -1, -1};
		int idx = LB(ALL(stor[i]), tmp) - stor[i].begin();
		if (idx == SZ(stor[i])) continue;
		res += stor[i][idx][1];
		pos = stor[i][idx][2];
	}
	return res;
}
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();
	// cerr << "Q = " << Q << endl;
	// 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 376 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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
24.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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1093 ms 1900 KB Output is correct
8 Correct 1124 ms 2916 KB Output is correct
9 Correct 867 ms 6028 KB Output is correct
10 Correct 640 ms 5880 KB Output is correct
11 Correct 652 ms 5816 KB Output is correct
12 Correct 1669 ms 6008 KB Output is correct
13 Correct 643 ms 5772 KB Output is correct

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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1093 ms 1900 KB Output is correct
8 Correct 1124 ms 2916 KB Output is correct
9 Correct 867 ms 6028 KB Output is correct
10 Correct 640 ms 5880 KB Output is correct
11 Correct 652 ms 5816 KB Output is correct
12 Correct 1669 ms 6008 KB Output is correct
13 Correct 643 ms 5772 KB Output is correct
14 Incorrect 351 ms 4172 KB Output isn't correct
15 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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1093 ms 1900 KB Output is correct
8 Correct 1124 ms 2916 KB Output is correct
9 Correct 867 ms 6028 KB Output is correct
10 Correct 640 ms 5880 KB Output is correct
11 Correct 652 ms 5816 KB Output is correct
12 Correct 1669 ms 6008 KB Output is correct
13 Correct 643 ms 5772 KB Output is correct
14 Incorrect 351 ms 4172 KB Output isn't correct
15 Halted 0 ms 0 KB -