oj.uz

답안 #199291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199291 2020-01-30T22:41:23 Z godwind 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 9000 ms 9208 KB 
// 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 = 250;

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3960 KB Output is correct
2 Correct 7 ms 3832 KB Output is correct
3 Correct 8 ms 3832 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3960 KB Output is correct
2 Correct 7 ms 3832 KB Output is correct
3 Correct 8 ms 3832 KB Output is correct
4 Correct 8 ms 3832 KB Output is correct
5 Correct 7 ms 3836 KB Output is correct
6 Correct 8 ms 3828 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3960 KB Output is correct
2 Correct 7 ms 3832 KB Output is correct
3 Correct 8 ms 3832 KB Output is correct
4 Correct 8 ms 3832 KB Output is correct
5 Correct 7 ms 3836 KB Output is correct
6 Correct 8 ms 3828 KB Output is correct
7 Correct 1170 ms 4816 KB Output is correct
8 Correct 1237 ms 4984 KB Output is correct
9 Correct 1564 ms 5752 KB Output is correct
10 Correct 2166 ms 6484 KB Output is correct
11 Correct 1807 ms 6560 KB Output is correct
12 Correct 2159 ms 6296 KB Output is correct
13 Correct 2326 ms 6564 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3960 KB Output is correct
2 Correct 7 ms 3832 KB Output is correct
3 Correct 8 ms 3832 KB Output is correct
4 Correct 8 ms 3832 KB Output is correct
5 Correct 7 ms 3836 KB Output is correct
6 Correct 8 ms 3828 KB Output is correct
7 Correct 1170 ms 4816 KB Output is correct
8 Correct 1237 ms 4984 KB Output is correct
9 Correct 1564 ms 5752 KB Output is correct
10 Correct 2166 ms 6484 KB Output is correct
11 Correct 1807 ms 6560 KB Output is correct
12 Correct 2159 ms 6296 KB Output is correct
13 Correct 2326 ms 6564 KB Output is correct
14 Correct 1672 ms 5576 KB Output is correct
15 Correct 1925 ms 5500 KB Output is correct
16 Correct 3016 ms 6268 KB Output is correct
17 Correct 3882 ms 7472 KB Output is correct
18 Correct 3785 ms 7384 KB Output is correct
19 Correct 4026 ms 7424 KB Output is correct
20 Correct 3949 ms 7672 KB Output is correct
21 Correct 3812 ms 7296 KB Output is correct
22 Correct 4218 ms 7444 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3960 KB Output is correct
2 Correct 7 ms 3832 KB Output is correct
3 Correct 8 ms 3832 KB Output is correct
4 Correct 8 ms 3832 KB Output is correct
5 Correct 7 ms 3836 KB Output is correct
6 Correct 8 ms 3828 KB Output is correct
7 Correct 1170 ms 4816 KB Output is correct
8 Correct 1237 ms 4984 KB Output is correct
9 Correct 1564 ms 5752 KB Output is correct
10 Correct 2166 ms 6484 KB Output is correct
11 Correct 1807 ms 6560 KB Output is correct
12 Correct 2159 ms 6296 KB Output is correct
13 Correct 2326 ms 6564 KB Output is correct
14 Correct 1672 ms 5576 KB Output is correct
15 Correct 1925 ms 5500 KB Output is correct
16 Correct 3016 ms 6268 KB Output is correct
17 Correct 3882 ms 7472 KB Output is correct
18 Correct 3785 ms 7384 KB Output is correct
19 Correct 4026 ms 7424 KB Output is correct
20 Correct 3949 ms 7672 KB Output is correct
21 Correct 3812 ms 7296 KB Output is correct
22 Correct 4218 ms 7444 KB Output is correct
23 Execution timed out 9056 ms 9208 KB Time limit exceeded
24 Halted 0 ms 0 KB -