Submission #199292

#	Time	Username	Problem	Language	Result	Execution time	Memory
199292		godwind	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9067 ms	9336 KiB

elephants

// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
// #include "grader.h"

using namespace std;


#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228

template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}

const int N = 150 * 1000 + 228;
const int K = 400;

int n, L;
int x[N], num[N];
int max_block;
vector<int> b[N];
int jump[N], right[N];

void build(int block) {
	int sz = (int)b[block].size();
	for (int i = sz - 1; i + 1; --i) {
		int l = i, r = sz;
		while (r - l > 1) {
			int m = (l + r) >> 1;
			if (x[b[block][m]] <= x[b[block][i]] + L) {
				l = m;
			} else {
				r = m;
			}
		}
		jump[b[block][i]] = sz - 1;
		if (l == sz - 1) {
			right[b[block][i]] = x[b[block][i]] + L;
			jump[b[block][i]] = 1;
		} else {
			right[b[block][i]] = right[b[block][l + 1]];
			jump[b[block][i]] = jump[b[block][l + 1]] + 1;
		}
	}
}

void rebuild() {
	vector<int> indices;
	for (int i = 0; i <= max_block; ++i) {
		for (int j : b[i]) {
			indices.emplace_back(j);
		}
		b[i].clear();
	}
	for (int i = 0; i < n; ++i) {
		b[i / K].push_back(indices[i]);
        num[indices[i]] = i / K;
	}
	for (int i = 0; i <= max_block; ++i) {
		build(i);
	}
}

int get_answer() {
	int block = 0;
	while (b[block].empty()) ++block;
	int ind = 0;
	int answer = 0;
	while (1) {
		int i = b[block][ind];
		answer += jump[i];
		if (block == max_block) break;
		bool caught = 0;
		for (int bl = block + 1; bl <= max_block; ++bl) {
			if (b[bl].empty()) continue;
			if (x[b[bl].back()] <= right[i]) continue;
			caught = 1;
			int l = -1, r = (int)b[bl].size() - 1;
			while (r - l > 1) {
				int m = (l + r) >> 1;
				if (x[b[bl][m]] <= right[i]) {
					l = m;
				} else {
					r = m;
				}
			}
			block = bl;
			ind = r;
			break;
		}
		if (!caught) break;
	}
	return answer;
}

int update(int id, int nv) {
	for (int i = 0; i < (int)b[num[id]].size(); ++i) {
		if (b[num[id]][i] == id) {
			b[num[id]].erase(b[num[id]].begin() + i);
		}
	}
	build(num[id]);
	x[id] = nv;
	int block = 0;
	for (int i = 0; i <= max_block; ++i) {
		if (!b[i].empty() && x[b[i][0]] <= x[id]) block = i;
	}
	b[block].push_back(id);
	num[id] = block;
	int pos = (int)b[block].size() - 1;
	while (pos && x[b[block][pos]] < x[b[block][pos - 1]]) {
		swap(b[block][pos], b[block][pos - 1]);
		--pos;
	}
	if (b[block].size() > 2 * K) {
		rebuild();
	} else {
		build(block);
	}
	// cout << "id=" << id << " nv=" << nv << endl;
	// for (int i = 0; i <= max_block; ++i) {
	// 	cout << "b[" << i << "] :\n";
	// 	for (int j : b[i]) {
	// 		cout << "(" << j << ", x=" << x[j] << ", jump=" << jump[j] << " right=" << right[j] << ")\n";
	// 	}
	// }
	return get_answer();
}

void init(int nnnn, int llll, int xs[]) {
	n = nnnn;
	L = llll;
	for (int i = 0; i < n; ++i) {
		x[i] = xs[i];
		b[i / K].push_back(i);
		num[i] = i / K;
	}
	max_block = (n - 1) / K;
	for (int i = 0; i <= max_block; ++i) {
		build(i);
	}
    return;
}

// int xx[100];

// signed main() {
// 	int q;
// 	cin >> n >> L >> q;
// 	for (int i = 0; i < n; ++i) {
// 		cin >> xx[i];
// 	}
// 	init(n, L, xx);
// 	while(q--) {
// 		int i, j;
// 		cin >> i >> j;
// 		cout << update(i, j) << '\n';
// 	}
// 	return 0;
// }

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