Submission #1867678


Source Code Expand

#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define rep(i,a,b) for(int32 i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int32 i = (b) - 1; i >= (a); --i)
#define bitget(a,b) (((a) >> (b)) & 1)
#define vint vector<int>
#define ALL(x) (x).begin(),(x).end()
#define C(x) cout << #x << " : " << x << endl
#define scanf scanf_s

using int32 = int_fast32_t;
using int64 = int_fast64_t;
using uint32 = uint_fast32_t;
using uint64 = uint_fast64_t;

using namespace std;
uint32 __builtin_ctzll(uint64 c) {
	uint32 t = 63;
	if (c & 0x00000000FFFFFFFF) { c = c & 0x00000000FFFFFFFF;t ^= 32; }
	if (c & 0x0000FFFF0000FFFF) { c = c & 0x0000FFFF0000FFFF;t ^= 16; }
	if (c & 0x00FF00FF00FF00FF) { c = c & 0x00FF00FF00FF00FF;t ^= 8; }
	if (c & 0x0F0F0F0F0F0F0F0F) { c = c & 0x0F0F0F0F0F0F0F0F;t ^= 4; }
	if (c & 0x3333333333333333) { c = c & 0x3333333333333333;t ^= 2; }
	if (c & 0x5555555555555555) { c = c & 0x5555555555555555;t ^= 1; }
	return t;
}
uint32 __builtin_clzll(uint64 c) {
	uint32 t = 63;
	if (c & 0xFFFFFFFF00000000) { c = c & 0xFFFFFFFF00000000;t ^= 32; }
	if (c & 0xFFFF0000FFFF0000) { c = c & 0xFFFF0000FFFF0000;t ^= 16; }
	if (c & 0xFF00FF00FF00FF00) { c = c & 0xFF00FF00FF00FF00;t ^= 8; }
	if (c & 0xF0F0F0F0F0F0F0F0) { c = c & 0xF0F0F0F0F0F0F0F0;t ^= 4; }
	if (c & 0xCCCCCCCCCCCCCCCC) { c = c & 0xCCCCCCCCCCCCCCCC;t ^= 2; }
	if (c & 0xAAAAAAAAAAAAAAAA) { c = c & 0xAAAAAAAAAAAAAAAA;t ^= 1; }
	return t;
}
uint64 bitmaskr[64] = { 0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFC, 0xFFFFFFFFFFFFFFF8, 0xFFFFFFFFFFFFFFF0, 0xFFFFFFFFFFFFFFE0, 0xFFFFFFFFFFFFFFC0, 0xFFFFFFFFFFFFFF80, 0xFFFFFFFFFFFFFF00, 0xFFFFFFFFFFFFFE00, 0xFFFFFFFFFFFFFC00, 0xFFFFFFFFFFFFF800, 0xFFFFFFFFFFFFF000, 0xFFFFFFFFFFFFE000, 0xFFFFFFFFFFFFC000, 0xFFFFFFFFFFFF8000, 0xFFFFFFFFFFFF0000, 0xFFFFFFFFFFFE0000, 0xFFFFFFFFFFFC0000, 0xFFFFFFFFFFF80000, 0xFFFFFFFFFFF00000, 0xFFFFFFFFFFE00000, 0xFFFFFFFFFFC00000, 0xFFFFFFFFFF800000, 0xFFFFFFFFFF000000, 0xFFFFFFFFFE000000, 0xFFFFFFFFFC000000, 0xFFFFFFFFF8000000, 0xFFFFFFFFF0000000, 0xFFFFFFFFE0000000, 0xFFFFFFFFC0000000, 0xFFFFFFFF80000000, 0xFFFFFFFF00000000, 0xFFFFFFFE00000000, 0xFFFFFFFC00000000, 0xFFFFFFF800000000, 0xFFFFFFF000000000, 0xFFFFFFE000000000, 0xFFFFFFC000000000, 0xFFFFFF8000000000, 0xFFFFFF0000000000, 0xFFFFFE0000000000, 0xFFFFFC0000000000, 0xFFFFF80000000000, 0xFFFFF00000000000, 0xFFFFE00000000000, 0xFFFFC00000000000, 0xFFFF800000000000, 0xFFFF000000000000, 0xFFFE000000000000, 0xFFFC000000000000, 0xFFF8000000000000, 0xFFF0000000000000, 0xFFE0000000000000, 0xFFC0000000000000, 0xFF80000000000000, 0xFF00000000000000, 0xFE00000000000000, 0xFC00000000000000, 0xF800000000000000, 0xF000000000000000, 0xE000000000000000, 0xC000000000000000, 0x8000000000000000, 0x0000000000000000 };
uint64 bitmaskl[64] = { 0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007, 0x000000000000000F, 0x000000000000001F, 0x000000000000003F, 0x000000000000007F, 0x00000000000000FF, 0x00000000000001FF, 0x00000000000003FF, 0x00000000000007FF, 0x0000000000000FFF, 0x0000000000001FFF, 0x0000000000003FFF, 0x0000000000007FFF, 0x000000000000FFFF, 0x000000000001FFFF, 0x000000000003FFFF, 0x000000000007FFFF, 0x00000000000FFFFF, 0x00000000001FFFFF, 0x00000000003FFFFF, 0x00000000007FFFFF, 0x0000000000FFFFFF, 0x0000000001FFFFFF, 0x0000000003FFFFFF, 0x0000000007FFFFFF, 0x000000000FFFFFFF, 0x000000001FFFFFFF, 0x000000003FFFFFFF, 0x000000007FFFFFFF, 0x00000000FFFFFFFF, 0x00000001FFFFFFFF, 0x00000003FFFFFFFF, 0x00000007FFFFFFFF, 0x0000000FFFFFFFFF, 0x0000001FFFFFFFFF, 0x0000003FFFFFFFFF, 0x0000007FFFFFFFFF, 0x000000FFFFFFFFFF, 0x000001FFFFFFFFFF, 0x000003FFFFFFFFFF, 0x000007FFFFFFFFFF, 0x00000FFFFFFFFFFF, 0x00001FFFFFFFFFFF, 0x00003FFFFFFFFFFF, 0x00007FFFFFFFFFFF, 0x0000FFFFFFFFFFFF, 0x0001FFFFFFFFFFFF, 0x0003FFFFFFFFFFFF, 0x0007FFFFFFFFFFFF, 0x000FFFFFFFFFFFFF, 0x001FFFFFFFFFFFFF, 0x003FFFFFFFFFFFFF, 0x007FFFFFFFFFFFFF, 0x00FFFFFFFFFFFFFF, 0x01FFFFFFFFFFFFFF, 0x03FFFFFFFFFFFFFF, 0x07FFFFFFFFFFFFFF, 0x0FFFFFFFFFFFFFFF, 0x1FFFFFFFFFFFFFFF, 0x3FFFFFFFFFFFFFFF, 0x7FFFFFFFFFFFFFFF };
struct VEBtip {
	uint32 root[2] = { ~static_cast<std::uint_fast32_t>(0) ,0 };
	std::vector<uint64> tree;
	uint64 aux = 0;
	VEBtip() :tree(64) {}
	//keyを挿入
	void insert(uint32 key) {
		if (!~root[0]) {
			root[0] = key;
			root[1] = key;
			return;
		}
		if (root[0] > key) {
			root[0] ^= key;
			key ^= root[0];
			root[0] ^= key;
		}
		else if (root[1] < key) {
			root[1] = key;
		}
		if (!tree[key >> 6]) {
			aux |= 1LL << (key >> 6);
		}
		tree[key >> 6] |= 1LL << (key & 63);
		return;
	}
	//keyを削除
	void erase(uint32 key) {
		if (root[0] == key) {
			if (root[1] == key) {
				root[0] = ~static_cast<std::uint_fast32_t>(0);
				root[1] = 0;
				return;
			}
			root[0] = (__builtin_ctzll(aux) << 6) | __builtin_ctzll(tree[__builtin_ctzll(aux)]);
			tree[root[0] >> 6] &= ~(1LL << (root[0] & 63));
			if (!tree[root[0] >> 6]) {
				aux &= ~(1LL << (root[0] >> 6));
			}
			return;
		}
		if (root[1] == key) {
			tree[key >> 6] &= ~(1LL << (key & 63));
			if (!tree[key >> 6]) {
				aux &= ~(1LL << (key >> 6));
			}
			if (aux) {
				root[1] = ((63 ^ (__builtin_clzll(aux))) << 6) | (63 ^ __builtin_clzll(tree[63 ^ __builtin_clzll(aux)]));
			}
			else {
				root[1] = root[0];
			}
			return;
		}
		tree[key >> 6] &= ~(1LL << (key & 63));
		if (!tree[key >> 6]) {
			aux &= ~(1LL << (key >> 6));
		}
		return;
	}
	//keyが存在するか
	bool find(const uint32 &key) {
		return tree[key >> 6] >> (key & 63) & 1 || root[0] == key;
	}
	//keyより大きい最小の要素
	uint32 findnext(const uint32 &key) {
		if (root[0] > key) {
			return root[0];
		}
		if (tree[key >> 6] & bitmaskr[key & 63]) {
			return (key & 4032) | __builtin_ctzll(tree[key >> 6] & bitmaskr[key & 63]);
		}
		return (__builtin_ctzll(aux&bitmaskr[key >> 6]) << 6) | __builtin_ctzll(tree[__builtin_ctzll(aux&bitmaskr[key >> 6])]);
	}
	//keyより小さい最大の要素
	uint32 findprev(const uint32 &key) {
		if (tree[key >> 6] & bitmaskl[key & 63]) {
			return (key & 4032) | (63 ^ __builtin_clzll(tree[key >> 6] & bitmaskl[key & 63]));
		}
		if (aux&bitmaskl[key >> 6]) {
			return ((63 ^ (__builtin_clzll(aux&bitmaskl[key >> 6]))) << 6) | (63 ^ __builtin_clzll(tree[63 ^ __builtin_clzll(aux&bitmaskl[key >> 6])]));
		}
		return root[0];
	}
};

class VEBTree {
	uint32 root[2] = { ~static_cast<std::uint_fast32_t>(0),0 };
	vector<VEBtip> tree;
	VEBtip aux;
public:
	VEBTree() :tree(4096) {}
	//集合が空か
	bool empty() {
		return !~root[0];
	}
	//最小値
	uint32 _min() {
		return root[0];
	}
	//最大値
	uint32 _max() {
		return root[1];
	}
	//keyを挿入
	void insert(uint32 key) {
		if (!~root[0]) {
			root[0] = key;
			root[1] = key;
			return;
		}
		if (root[0] > key) {
			root[0] ^= key;
			key ^= root[0];
			root[0] ^= key;
		}
		else if (root[1] < key) {
			root[1] = key;
		}
		if (!~tree[key >> 12].root[0]) {
			aux.insert(key >> 12);
		}
		tree[key >> 12].insert(key & 4095);
		return;
	}
	//keyを削除
	void erase(uint32 key) {
		if (root[0] == key) {
			if (root[1] == key) {
				root[0] = ~static_cast<std::uint_fast32_t>(0);
				root[1] = 0;
				return;
			}
			root[0] = aux.root[0] << 12 | tree[aux.root[0]].root[0];
			tree[root[0] >> 12].erase(root[0] & 4095);
			if (!~tree[root[0] >> 12].root[0]) {
				aux.erase(root[0] >> 12);
			}
			return;
		}
		tree[key >> 12].erase(key & 4095);
		if (!~tree[key >> 12].root[0]) {
			aux.erase(key >> 12);
		}
		if (root[1] == key) {
			if (!~aux.root[0]) {
				root[1] = root[0];
				return;
			}
			root[1] = aux.root[1] << 12 | tree[aux.root[1]].root[1];
			return;
		}
		return;
	}
	//keyが存在するか
	bool find(const uint32 &key) {
		if (key >= 16777215) return false;
		return tree[key >> 12].find(key & 4095) || root[0] == key;
	}
	//keyより大きい最小の要素
	uint32 findnext(const uint32 &key) {
		if (root[1] <= key) {
			return ~static_cast<std::uint_fast32_t>(0);
		}
		if (root[0] > key) {
			return root[0];
		}
		if (tree[key >> 12].root[1] <= (key & 4095)) {
			return aux.findnext(key >> 12) << 12 | tree[aux.findnext(key >> 12)].root[0];
		}
		return key & 16773120 | tree[key >> 12].findnext(key & 4095);
	}
	//keyより小さい最大の要素
	uint32 findprev(const uint32 &key) {
		if (root[0] >= key) {
			return ~static_cast<std::uint_fast32_t>(0);
		}
		if (root[1] < key) {
			return root[1];
		}
		if (!tree[key >> 12].root[0] >= (key & 4095)) {
			return key & 16773120 | tree[key >> 12].findprev(key & 4095);
		}
		if (aux.root[0] > (key >> 12)) {
			return root[0];
		}
		return aux.findprev(key >> 12) << 12 | tree[aux.findprev(key >> 12)].root[1];
	}
};


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	VEBTree t;
	uint32 q;
	uint32 s = 0;
	cin >> q;
	uint32 y, x;
	uint32 temp;
	rep(i, 0, q) {
		cin >> y >> x;
		if (y == 1) {
			t.insert(x);
			++s;
		}
		else {
			temp = t._max();
			rep(j, 0, s - x) {
				temp = t.findprev(temp);
			}
			cout << temp << endl;
			t.erase(temp);
			--s;
		}
	}
	return 0;
}

Submission Info

Submission Time
Task C - データ構造
User noshi91
Language C++14 (GCC 5.4.1)
Score 0
Code Size 9507 Byte
Status RE
Exec Time 2103 ms
Memory 2816 KB

Compile Error

./Main.cpp: In function ‘uint32 __builtin_ctzll(uint64)’:
./Main.cpp:32:32: warning: new declaration ‘uint32 __builtin_ctzll(uint64)’ ambiguates built-in declaration ‘int __builtin_ctzll(long long unsigned int)’
 uint32 __builtin_ctzll(uint64 c) {
                                ^
./Main.cpp: In function ‘uint32 __builtin_clzll(uint64)’:
./Main.cpp:42:32: warning: new declaration ‘uint32 __builtin_clzll(uint64)’ ambiguates built-in declaration ‘int __builtin_clzll(long long unsigned int)’
 uint32 __builtin_clzll(uint64 c) {
                                ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 1
WA × 1
AC × 4
WA × 5
TLE × 5
RE × 4
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt
Case Name Status Exec Time Memory
sample_01.txt WA 2 ms 2560 KB
sample_02.txt AC 2 ms 2560 KB
subtask1_01.txt AC 2 ms 2560 KB
subtask1_02.txt AC 2 ms 2560 KB
subtask1_03.txt WA 3 ms 2560 KB
subtask1_04.txt RE 104 ms 2560 KB
subtask1_05.txt WA 35 ms 2688 KB
subtask1_06.txt WA 3 ms 2560 KB
subtask1_07.txt WA 1887 ms 2688 KB
subtask1_08.txt RE 152 ms 2688 KB
subtask1_09.txt RE 168 ms 2816 KB
subtask1_10.txt TLE 2103 ms 2816 KB
subtask1_11.txt TLE 2103 ms 2816 KB
subtask1_12.txt AC 29 ms 2560 KB
subtask1_13.txt TLE 2103 ms 2688 KB
subtask1_14.txt TLE 2103 ms 2688 KB
subtask1_15.txt TLE 2103 ms 2560 KB
subtask1_16.txt RE 98 ms 2560 KB