QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#853577#9727. Barkley IIIucup-team191#WA 4ms38748kbC++232.9kb2025-01-11 17:39:262025-01-11 17:39:27

Judging History

你现在查看的是最新测评结果

  • [2025-01-13 03:55:43]
  • hack成功,自动添加数据
  • (/hack/1447)
  • [2025-01-11 17:39:27]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:38748kb
  • [2025-01-11 17:39:26]
  • 提交

answer

#include <bits/stdc++.h>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

const int N = 1e5 + 500;
const int OFF = (1 << 20);
const ll MSK = (1ULL << 63) - 1;

inline pll spoji(const pll &A, const pll &B) {
	return {A.X & B.X, (A.Y & B.X) | (A.X & B.Y)}; 
}

ll prop[2 * OFF];
pll T[2 * OFF];
int n, q;

void refresh(int x) {
	if(prop[x] == MSK) return;
	if(x < OFF) {
		T[x] = {T[x].X & prop[x], T[x].Y & prop[x]};
		prop[2 * x] &= prop[x];
		prop[2 * x + 1] &= prop[x];
	} else {
		T[x].X &= prop[x];
		T[x].Y = (T[x].Y | ~prop[x]) & MSK;
	}
	prop[x] = MSK;
}

void update(int i, int a, int b, int lo, int hi, ll x) {
	if(lo <= a && b <= hi) {
		prop[i] &= x; refresh(i);
		return;
	}
	refresh(i);
	if(a > hi || b < lo) return;
	update(2 * i, a, (a + b) / 2, lo, hi, x);
	update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
	T[i] = spoji(T[2 * i], T[2 * i + 1]);
}

pll query(int i, int a, int b, int lo, int hi) {
	refresh(i);
	if(lo <= a && b <= hi) return T[i];
	if(a > hi || b < lo) return {MSK, 0};
	return spoji(query(2 * i, a, (a + b) / 2, lo, hi), query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}

int get_index(int i, int a, int b, int lo, int hi, ll tko) {
	if(a > hi || b < lo || (T[i].X & tko)) return 0;
	if(i >= OFF) return i - OFF;
	return get_index(2 * i, a, (a + b) / 2, lo, hi, tko) + get_index(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, tko);
}

void sett(int i, int a, int b, int pos, ll sto) {
	refresh(i);
	if(i == OFF + pos) {
		T[i] = {sto, (~sto) & MSK};
		return;
	}
	if(pos <= (a + b) / 2) {
		refresh(2 * i + 1);
		sett(2 * i, a, (a + b) / 2, pos, sto);
	} else {
		refresh(2 * i);
		sett(2 * i + 1, (a + b) / 2 + 1, b, pos, sto);
	}
	T[i] = spoji(T[2 * i], T[2 * i + 1]);
}

ll gett(int i, int a, int b, int pos) {
	refresh(i);
	if(i == OFF + pos) return T[i].X;
	if(pos <= (a + b) / 2) {
		return gett(2 * i, a, (a + b) / 2, pos);
	}
	return gett(2 * i + 1, (a + b) / 2 + 1, b, pos);
}

int main() {
	for(int i = 0;i < 2 * OFF;i++) prop[i] = MSK;
	scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++) {
		int x; scanf("%d", &x);
		T[OFF + i] = {x, (~x) & MSK};
	}
	for(int i = OFF - 1; i ;i--) T[i] = spoji(T[2 * i], T[2 * i + 1]);
	for(int i = 0;i < q;i++) {
		int ty; scanf("%d", &ty);
		if(ty == 1) {
			int l, r; ll x; scanf("%d%d%lld", &l, &r, &x); l--, r--;
			update(1, 0, OFF - 1, l, r, x);
		} else if(ty == 2) {
			int p; ll x; scanf("%d%lld", &p, &x); p--;
			sett(1, 0, OFF - 1, p, x);
		} else {
			int l, r; scanf("%d%d", &l, &r); l--, r--;
			pll res = query(1, 0, OFF - 1, l, r);
			if(!res.Y) {
				printf("%lld\n", res.X);
			} else {
				ll makni = 1LL << __lg(res.Y);	
				int los = get_index(1, 0, OFF - 1, l, r, makni);
				ll val = gett(1, 0, OFF - 1, los);
				printf("%lld\n", res.X | (res.Y & (~val)));
			}
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 38748kb

input:

5 9
7 7 7 6 7
3 1 5
2 1 3
3 1 5
3 1 3
1 1 2 3
3 1 3
2 2 8
3 1 3
3 1 2

output:

7
6
7
3
3
8

result:

ok 6 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 38656kb

input:

10 10
6760061359215711796 1568091718842717482 1568091718842717482 1568091718842717482 5232472783634052627 8795942500783873690 1568091718842717482 1568091718842717482 1568091718842717482 1568091718842717482
1 3 5 7587422031989082829
3 6 10
1 7 8 5197616143400216932
2 4 2518604563805514908
2 2 4533959...

output:

886707498
536870912
537919776
9223372036854505114

result:

wrong answer 1st lines differ - expected: '1568091718842717482', found: '886707498'