提交记录 8986


用户 题目 状态 得分 用时 内存 语言 代码长度
Dustii noi17a. 【NOI2017】整数 Accepted 100 373.156 ms 19076 KB C++11 2.21 KB
提交时间 评测时间
2019-03-30 19:03:38 2020-08-01 01:28:31
#include <set>
#include <cstdio>
#include <cctype>
#include <bitset>

const int ioSize = 1 << 21 | 1;
char iBuf[ioSize], *iS, *iE;
inline char getc() { return iS == iE ? iE = iBuf + fread(iS = iBuf, 1, ioSize, stdin), iS == iE ? EOF : *iS++ : *iS++; }
void readi(int &x)
{
	char c;
	bool isneg = false;
	for (c = getc(); !isdigit(c) && c != '-'; c = getc())
		;
	if (c == '-')
		isneg = true, c = getc();
	x = c ^ '0';
	for (c = getc(); isdigit(c); c = getc())
		(x *= 10) += c ^ '0';
	if (isneg)
		x = -x;
}

typedef unsigned long long ull;
const int base = 60, maxN = 1000005;
const ull MAX = (1ULL << 60) - 1;

ull A[maxN], B[maxN];
std::set<int> diffPos;

void add(int x)
{
	int block = x / base;
	x %= base;
	ull temp = 1ULL << x;
	while (temp)
	{
		ull old = A[block];
		A[block] += temp;
		temp = A[block] >> base;
		A[block] &= MAX;
		if (old == B[block] && A[block] != B[block])
			diffPos.insert(block);
		if (old != B[block] && A[block] == B[block])
			diffPos.erase(block);
		++block;
	}
}

void minus(int x)
{
	int block = x / base;
	x %= base;
	ull temp = 1ULL << x;
	while (temp)
	{
		ull old = B[block];
		B[block] += temp;
		temp = B[block] >> base;
		B[block] &= MAX;
		if (A[block] == old && A[block] != B[block])
			diffPos.insert(block);
		if (A[block] != old && A[block] == B[block])
			diffPos.erase(block);
		++block;
	}
}

int query(int x)
{
	int block = x / base;
	x %= base;
	int ans = (A[block] >> x & 1) ^ (B[block] >> x & 1);
	ull temp = A[block] ^ B[block];
	temp &= (1ULL << x) - 1;
	if (!temp)
	{
		auto it = diffPos.lower_bound(block);
		if (it != diffPos.begin())
		{
			--it;
			block = *it;
			temp = A[block] ^ B[block];
		}
	}
	if (temp)
	{
		int pos = 63 - __builtin_clzll(temp);
		if ((A[block] >> pos & 1) < (B[block] >> pos & 1))
			ans ^= 1;
	}
	return ans;
}

int main()
{
	int n, t1, t2, t3;

	readi(n), readi(t1), readi(t2), readi(t3);

	for (int o, a, b, k; n--;)
	{
		readi(o);
		if (o == 1)
		{
			readi(a), readi(b);
			if (a > 0)
			{
				for (int i = 0; i != 30; ++i)
					if (a >> i & 1)
						add(b + i);
			}
			else if (a < 0)
			{
				a = -a;
				for (int i = 0; i != 30; ++i)
					if (a >> i & 1)
						minus(b + i);
			}
		}
		else
		{
			readi(k);
			printf("%d\n", query(k));
		}
	}

	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #117.36 us36 KBAcceptedScore: 4

Testcase #250.26 us36 KBAcceptedScore: 4

Testcase #3492.41 us56 KBAcceptedScore: 4

Testcase #4560.8 us72 KBAcceptedScore: 4

Testcase #51.669 ms120 KBAcceptedScore: 4

Testcase #6837.28 us116 KBAcceptedScore: 4

Testcase #72.676 ms328 KBAcceptedScore: 4

Testcase #82.584 ms184 KBAcceptedScore: 4

Testcase #99.11 ms1020 KBAcceptedScore: 4

Testcase #1014.052 ms1 MB + 88 KBAcceptedScore: 4

Testcase #1115.985 ms992 KBAcceptedScore: 4

Testcase #129.419 ms1 MB + 656 KBAcceptedScore: 4

Testcase #1321.945 ms2 MB + 292 KBAcceptedScore: 4

Testcase #1465 ms5 MB + 368 KBAcceptedScore: 4

Testcase #1548.01 ms6 MB + 400 KBAcceptedScore: 4

Testcase #16134.885 ms8 MB + 696 KBAcceptedScore: 4

Testcase #17136.72 ms2 MB + 848 KBAcceptedScore: 4

Testcase #18212.721 ms12 MB + 16 KBAcceptedScore: 4

Testcase #19251.404 ms13 MB + 672 KBAcceptedScore: 4

Testcase #20344.072 ms17 MB + 440 KBAcceptedScore: 4

Testcase #21170.416 ms15 MB + 120 KBAcceptedScore: 4

Testcase #22255.298 ms3 MB + 528 KBAcceptedScore: 4

Testcase #23283.253 ms6 MB + 512 KBAcceptedScore: 4

Testcase #24271.679 ms3 MB + 628 KBAcceptedScore: 4

Testcase #25373.156 ms18 MB + 644 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-28 16:38:57 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用