QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#468798#8338. Quad Kingdoms Chessreal_sigma_teamWA 100ms104628kbC++205.8kb2024-07-09 01:02:162024-07-09 01:02:16

Judging History

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

  • [2024-07-09 01:02:16]
  • 评测
  • 测评结果:WA
  • 用时:100ms
  • 内存:104628kb
  • [2024-07-09 01:02:16]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define x first
#define y second

void solve();

int main() {
#ifdef LOCAL
	cin.tie(nullptr)->sync_with_stdio(false);
#endif
	cout << fixed << setprecision(30);
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
}

mt19937_64 mt(time(nullptr));

const int N = 100100, K = 1100, mod = 100'000'007;
int a[N], b[N], prv[mod], sufa[N], sufb[N], prva[K], suffa[K], prvb[K], suffb[K], mna[N], mnb[N], inda[K], indb[K];
unsigned long long hsh[N], prefa[N], prefb[N];
pair<int, int> cha[K], chb[K], stk[N], chas[K], chbs[K];
pair<int, pair<int, int>> que[2 * N], chall[K];


void solve() {
	for (int i = 0; i < N; i++) {
		hsh[i] = mt();
	}
	int n1, n2, q;
	cin >> n1;
	for (int i = 0; i < n1; i++) {
		cin >> a[i];
	}
	cin >> n2;
	for (int i = 0; i < n2; i++) {
		cin >> b[i];
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> que[i].x >> que[i].y.x >> que[i].y.y; que[i].y.x--;
	}
	for (int st = 0; st < q; st += K) {
		int sz = min(K, q - st);
		for (int i = 0; i < n1; i++) {
			mna[i] = a[i];
		}
		for (int i = 0; i < n2; i++) {
			mnb[i] = b[i];
		}
		int indasz = 0, indbsz = 0;
		set<int> ia, ib;
		for (int i = 0; i < sz; i++) {
			chall[i] = que[i + st];
			if (chall[i].x == 1) {
				mna[chall[i].y.x] = min(mna[chall[i].y.x], chall[i].y.y);
				ia.insert(chall[i].y.x);
			} else {
				mnb[chall[i].y.x] = min(mnb[chall[i].y.x], chall[i].y.y);
				ib.insert(chall[i].y.x);
			}
		}
		for (int i : ia) {
			inda[indasz++] = i;
		}
		for (int i : ib) {
			indb[indbsz++] = i;
		}
		{
			sufa[n1 - 1] = 0;
			for (int i = n1 - 2; i >= 0; i--) {
				sufa[i] = max(sufa[i + 1], mna[i + 1]);
			}
			prefa[0] = 0;
			for (int i = 0; i < n1; i++) {
				if (mna[i] >= sufa[i]) {
					prefa[i + 1] = prefa[i] + hsh[mna[i]];
				} else {
					prefa[i + 1] = prefa[i];
				}
			}
			int chassz = 0;
			for (int i = 0; i < sz; i++) {
				if (chall[i].x == 1) {
					chas[chassz++] = chall[i].y;
					chas[chassz++] = {chall[i].y.x, a[chall[i].y.x]};
				}
			}
			sort(chas, chas + chassz);
			int stksz = 1, ptr = 0;
			stk[0] = {INT32_MAX, -1};
			for (int i = 0; i < n1; i++) {
				while (mna[i] >= stk[stksz - 1].x) {
					stksz--;
				}
				stk[stksz++] = {mna[i], i};
				while (ptr < chassz && chas[ptr].x == i) {
					int nw = stksz;
					for (int l = 17; l >= 0; l--) {
						if (nw - (1 << l) >= 0 && stk[nw - (1 << l)].x < chas[ptr].y) {
							nw -= (1 << l);
						}
					}
					nw--;
					prv[(hsh[chas[ptr].x] + hsh[31] * hsh[chas[ptr].y] + hsh[0]) % mod] = stk[nw].y;
					ptr++;
				}
			}
		}
		{
			sufb[n2 - 1] = 0;
			for (int i = n2 - 2; i >= 0; i--) {
				sufb[i] = max(sufb[i + 1], mnb[i + 1]);
			}
			prefb[0] = 0;
			for (int i = 0; i < n2; i++) {
				if (mnb[i] >= sufb[i]) {
					prefb[i + 1] = prefb[i] + hsh[mnb[i]];
				} else {
					prefb[i + 1] = prefb[i];
				}
			}
			int chbssz = 0;
			for (int i = 0; i < sz; i++) {
				if (chall[i].x == 2) {
					chbs[chbssz++] = chall[i].y;
					chbs[chbssz++] = {chall[i].y.x, b[chall[i].y.x]};
				}
			}
			sort(chbs, chbs + chbssz);
			int stksz = 1, ptr = 0;
			stk[0] = {INT32_MAX, -1};
			for (int i = 0; i < n2; i++) {
				while (mnb[i] >= stk[stksz - 1].x) {
					stksz--;
				}
				stk[stksz++] = {mnb[i], i};
				while (ptr < chbssz && chbs[ptr].x == i) {
					int nw = stksz;
					for (int l = 17; l >= 0; l--) {
						if (nw - (1 << l) >= 0 && stk[nw - (1 << l)].x < chbs[ptr].y) {
							nw -= (1 << l);
						}
					}
					nw--;
					prv[(hsh[chbs[ptr].x] + hsh[31] * hsh[chbs[ptr].y] + hsh[1]) % mod] = stk[nw].y;
					ptr++;
				}
			}
		}
		unsigned long long resmna = prefa[n1], resmnb = prefb[n2];
		for (int c = 0; c < sz; c++) {
			int chasz = 0, chbsz = 0;
			unsigned long long resa = resmna, resb = resmnb;
			if (chall[c].x == 1) {
				a[chall[c].y.x] = chall[c].y.y;
			} else {
				b[chall[c].y.x] = chall[c].y.y;
			}
			{
				for (int i = 0; i < indasz; i++) {
					if (mna[inda[i]] != a[inda[i]]) {
						cha[chasz++] = {inda[i], a[inda[i]]};
					}
				}
				int stksz = 1;
				stk[0] = {INT32_MAX, -1};
				for (int i = 0; i < chasz; i++) {
					while (cha[i].y > stk[stksz - 1].x) {
						stksz--;
					}
					prva[i] = stk[stksz - 1].y;
					stk[stksz++] = {cha[i].y, cha[i].x};
				}
				suffa[chasz - 1] = 0;
				for (int i = chasz - 2; i >= 0; i--) {
					suffa[i] = max(suffa[i + 1], cha[i + 1].y);
				}
				for (int i = 0; i < chasz; i++) {
					if (max(suffa[i], sufa[cha[i].x]) > cha[i].y) {
						continue;
					}
					int r = cha[i].x + 1;
					int l;
					int c1 = prva[i], c2 = prv[(hsh[cha[i].x] + hsh[31] * hsh[cha[i].y] + hsh[0]) % mod];
					if (a[c1] > a[c2]) {
						l = c1 + 1;
					} else if (a[c2] > a[c1]) {
						l = c2 + 1;
					} else {
						l = max(c1, c2) + 1;
					}
					resa -= prefa[r] - prefa[l];
					resa += hsh[cha[i].y];
				}
			}
			{
				for (int i = 0; i < indbsz; i++) {
					if (mnb[indb[i]] != b[indb[i]]) {
						chb[chbsz++] = {indb[i], b[indb[i]]};
					}
				}
				int stksz = 1;
				stk[0] = {INT32_MAX, -1};
				for (int i = 0; i < chbsz; i++) {
					while (chb[i].y > stk[stksz - 1].x) {
						stksz--;
					}
					prvb[i] = stk[stksz - 1].y;
					stk[stksz++] = {chb[i].y, chb[i].x};
				}
				suffb[chbsz - 1] = 0;
				for (int i = chbsz - 2; i >= 0; i--) {
					suffb[i] = max(suffb[i + 1], chb[i + 1].y);
				}
				for (int i = 0; i < chbsz; i++) {
					if (max(suffb[i], sufb[chb[i].x]) > chb[i].y) {
						continue;
					}
					int r = chb[i].x + 1;
					int l;
					int c1 = prvb[i], c2 = prv[(hsh[chb[i].x] + hsh[31] * hsh[chb[i].y] + hsh[1]) % mod];
					if (b[c1] > b[c2]) {
						l = c1 + 1;
					} else if (b[c2] > b[c1]) {
						l = c2 + 1;
					} else {
						l = max(c1, c2) + 1;
					}
					resb -= prefb[r] - prefb[l];
					resb += hsh[chb[i].y];
				}
			}
			cout << (resa == resb ? "YES\n" : "NO\n");
			// cout << resa << ' ' << resb << '\n';
		}
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 34676kb

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: 79ms
memory: 38576kb

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: 83ms
memory: 35772kb

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: 0
Accepted
time: 99ms
memory: 74248kb

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:

ok 200000 tokens

Test #5:

score: 0
Accepted
time: 77ms
memory: 34584kb

input:

4
1 1 2 2
1
1
200000
2 1 2
1 1 3
1 2 1
2 1 2
2 1 2
2 1 3
2 1 1
2 1 1
1 4 2
2 1 3
1 3 1
1 2 1
1 3 2
2 1 1
1 4 2
2 1 1
2 1 2
1 1 1
2 1 2
2 1 1
1 4 1
1 2 2
2 1 1
1 1 1
1 4 3
2 1 3
1 1 3
2 1 2
1 2 1
2 1 1
2 1 1
2 1 1
2 1 3
2 1 2
1 2 3
2 1 3
1 3 3
2 1 1
1 2 3
2 1 2
1 1 2
2 1 2
2 1 3
1 2 1
1 4 3
2 1 2
2 1...

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
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
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 200000 tokens

Test #6:

score: 0
Accepted
time: 90ms
memory: 49440kb

input:

2
4 2
4
2 3 3 2
200000
1 1 2
1 2 2
1 2 2
1 2 4
1 1 2
1 2 4
2 2 1
1 1 3
2 3 2
2 3 1
2 2 4
2 3 2
2 2 1
1 1 4
1 2 4
2 2 1
1 1 2
2 1 2
2 4 4
1 2 4
1 2 3
2 4 4
2 3 1
2 1 3
2 3 1
2 2 1
1 1 2
2 2 1
1 2 3
1 2 2
1 2 1
1 2 4
1 2 4
1 1 3
1 1 4
2 1 3
1 1 1
1 2 4
2 1 2
2 3 4
1 2 4
2 2 1
1 2 1
2 3 2
1 2 3
2 3 3
1...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
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
NO
NO
NO
NO
NO
NO
N...

result:

ok 200000 tokens

Test #7:

score: 0
Accepted
time: 93ms
memory: 98360kb

input:

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

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
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 200000 tokens

Test #8:

score: 0
Accepted
time: 88ms
memory: 92256kb

input:

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

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 #9:

score: 0
Accepted
time: 100ms
memory: 104628kb

input:

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

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
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
NO
NO
NO
NO
NO
NO...

result:

ok 200000 tokens

Test #10:

score: -100
Wrong Answer
time: 84ms
memory: 58096kb

input:

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

output:

NO
NO
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
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
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

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