QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#734972#8338. Quad Kingdoms Chesswarner1129WA 1ms4356kbC++201.6kb2024-11-11 16:21:042024-11-11 16:21:05

Judging History

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

  • [2024-11-11 16:21:05]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4356kb
  • [2024-11-11 16:21:04]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

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

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{}, lh{};
	u64 get(int x) {
		if (ma < x) {
			return 0;
		}
		if (mi >= x) {
			return h;
		}
		if (x >= rs->ma) {
			return ls->get(x) + rs->h;
		}
		return lh + rs->get(x);
	}
	void pull() {
		ma = max(ls->ma, rs->ma);
		mi = min(ls->mi, rs->mi);
		lh = ls->get(rs->ma);
		h = lh + 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: 0
Wrong Answer
time: 1ms
memory: 4356kb

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
NO

result:

wrong answer 8th words differ - expected: 'YES', found: 'NO'