QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#734936#8338. Quad Kingdoms Chesswarner1129WA 25ms4752kbC++141.5kb2024-11-11 16:08:022024-11-11 16:08:04

Judging History

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

  • [2024-11-11 16:08:04]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:4752kb
  • [2024-11-11 16:08:02]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
using u64 = unsigned long long;

mt19937 rng(time(0));
constexpr u64 P = 1E9 + 321;
constexpr int kC = 1E5;

u64 pw[kC + 1];

struct Seg {
	Seg *ls{}, *rs{};
	int l, r;
	int ma, mi;
	u64 h{};
	u64 get(int x) {
		if (ma < x) {
			return 0;
		}
		if (mi >= x) {
			return h;
		}
		return ls->get(x) + rs->get(x);
	}
	void pull() {
		ma = max(ls->ma, rs->ma);
		mi = min(ls->mi, rs->mi);
		h = ls->get(rs->ma) + rs->h;
	}
	Seg(int _l, int _r, const vector<int> &v) : l(_l), r(_r) {
		if (r - l == 1) {
			ma = mi = v[l];
			h = pw[v[l]];
			return;
		}
		int m = (l + r) / 2;
		ls = new Seg(l, m, v);
		rs = new Seg(m, r, v);
		pull();
	}
	void set(int p, int v) {
		if (r - l == 1) {
			h = pw[v];
			ma = mi = v;
			return;
		}
		int m = (l + r) / 2;
		if (p < m) {
			ls->set(p, v);
		} else {
			rs->set(p, v);
		}
		pull();
	}
};

void solve() {
	vector<int> tmp;

	int n;
	cin >> n;

	tmp.resize(n);
	for (int &x : tmp) {
		cin >> x;
	}
	Seg A(0, n, tmp);

	int m;
	cin >> m;
	tmp.resize(m);
	for (int &x : tmp) {
		cin >> x;
	}
	Seg B(0, m, tmp);

	int q;
	cin >> q;
	while (q--) {
		int o, p, v;
		cin >> o >> p >> v;
		p--;

		(o == 1 ? A : B).set(p, v);

		if (A.get(-1) == B.get(-1)) {
			cout << "YES\n";
		} else {
			cout << "NO\n";
		}
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(false);

	pw[0] = 1;
	for (int i = 1; i <= kC; i++) {
		pw[i] = pw[i - 1] * P;
	}

	solve();

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4424kb

input:

5
1 2 3 4 5
5
5 4 3 2 1
8
1 1 5
1 4 2
1 2 4
1 5 1
1 5 5
2 1 4
2 3 5
2 5 5

output:

NO
NO
NO
YES
NO
NO
NO
YES

result:

ok 8 tokens

Test #2:

score: 0
Accepted
time: 25ms
memory: 4752kb

input:

1
2
6
2 1 1 1 1 1
200000
2 6 2
1 1 1
1 1 1
1 1 2
2 1 1
1 1 2
1 1 1
2 4 1
2 1 2
1 1 1
1 1 2
2 5 1
1 1 1
1 1 2
1 1 1
2 6 1
1 1 2
1 1 2
1 1 2
2 3 1
1 1 1
2 1 1
2 6 2
1 1 2
2 4 1
1 1 2
2 6 1
1 1 2
1 1 1
2 5 2
2 6 2
1 1 1
2 4 2
2 5 2
2 6 2
1 1 1
2 5 1
2 6 2
1 1 2
1 1 1
1 1 1
2 4 1
1 1 2
1 1 2
1 1 2
2 3 2...

output:

NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 200000 tokens

Test #3:

score: 0
Accepted
time: 20ms
memory: 4560kb

input:

6
2 1 1 2 1 2
1
1
200000
2 1 1
1 1 2
1 1 1
2 1 2
2 1 1
2 1 1
2 1 2
2 1 2
1 1 2
1 3 1
1 6 2
1 5 2
1 4 2
1 3 1
2 1 2
1 4 2
1 4 2
2 1 2
2 1 2
1 3 1
1 6 1
1 1 2
2 1 1
1 6 1
1 3 1
1 5 2
1 6 2
1 5 2
2 1 2
1 2 1
1 5 2
2 1 1
2 1 1
1 6 1
2 1 2
2 1 1
1 3 2
2 1 1
1 6 1
1 4 2
1 2 1
1 1 1
2 1 1
1 2 1
1 6 2
1 6 2...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 tokens

Test #4:

score: -100
Wrong Answer
time: 25ms
memory: 4432kb

input:

6
1 3 1 2 1 2
6
2 1 3 3 3 1
200000
2 4 2
1 2 1
1 6 2
2 3 2
1 1 1
1 6 2
1 6 2
1 3 2
2 6 1
2 4 3
1 1 2
2 5 2
2 6 2
2 3 1
1 4 3
1 3 1
2 5 2
2 4 2
2 1 3
1 1 1
2 2 2
2 4 2
1 5 3
1 6 3
2 6 3
1 5 3
2 5 3
2 4 1
2 4 2
1 1 2
1 6 1
2 6 1
1 2 3
1 1 3
1 1 1
2 6 3
2 4 1
1 4 2
2 2 1
1 3 1
1 1 3
1 1 3
1 4 3
1 3 3
2...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

wrong answer 1061st words differ - expected: 'YES', found: 'NO'