QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#627683#5541. Substring Sortucup-team5062#WA 1300ms10360kbC++207.5kb2024-10-10 16:44:432024-10-10 16:44:43

Judging History

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

  • [2024-10-10 16:44:43]
  • 评测
  • 测评结果：WA
  • 用时：1300ms
  • 内存：10360kb
查看
  • [2024-10-10 16:44:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int BACKET = 300;
int N;
int Q, L[1 << 19], R[1 << 19];
int Lexico[1 << 19][3][3];
int Orders[1 << 19][3];
string S[3];


// ======================================================================== Base Function
// -1: idx1 is smaller
//  0: same
// +1: idx1 is larger
int Compare(int pos, int idx1, int idx2) {
	int cl = pos * BACKET;
	int cr = pos * BACKET + BACKET; cr = min(cr, N);
	int ord1 = Orders[pos][idx1];
	int ord2 = Orders[pos][idx2];
	for (int i = cl; i < cr; i++) {
		if (S[ord1][i] < S[ord2][i]) return -1;
		if (S[ord1][i] > S[ord2][i]) return +1;
	}
	return 0;
}

int FastCompare(int cl, int cr, int idx1, int idx2) {
	int backet_l = cl / BACKET + 1;
	int backet_r = cr / BACKET;

	// First Compare
	int fst_ord1 = Orders[backet_l - 1][idx1];
	int fst_ord2 = Orders[backet_l - 1][idx2];
	for (int i = cl; i < backet_l * BACKET; i++) {
		if (S[fst_ord1][i] < S[fst_ord2][i]) return -1;
		if (S[fst_ord1][i] > S[fst_ord2][i]) return +1;
	}

	// Second Compare
	for (int i = backet_l; i < backet_r; i++) {
		int snd_ord1 = Orders[i][idx1];
		int snd_ord2 = Orders[i][idx2];
		if (Lexico[i][snd_ord1][snd_ord2] == -1) return -1;
		if (Lexico[i][snd_ord1][snd_ord2] == +1) return +1;
	}

	// Last Compare
	int srd_ord1 = Orders[backet_r][idx1];
	int srd_ord2 = Orders[backet_r][idx2];
	for (int i = backet_r * BACKET; i < cr; i++) {
		if (S[srd_ord1][i] < S[srd_ord2][i]) return -1;
		if (S[srd_ord1][i] > S[srd_ord2][i]) return +1;
	}
	return 0;
}


// ======================================================================== Update Function
void Update(int cl, int cr, int fst, int snd, int srd) {
	int backet_l = cl / BACKET + 1;
	int backet_r = cr / BACKET;

	// Middle Update
	for (int i = backet_l; i < backet_r; i++) {
		int v[3] = {Orders[i][0], Orders[i][1], Orders[i][2]};
		Orders[i][0] = v[fst];
		Orders[i][1] = v[snd];
		Orders[i][2] = v[srd];
	}

	// Case 1
	if (backet_l - 1 == backet_r) {
		string sub[3] = {"", "", ""};
		int pl = (backet_l - 1) * BACKET;
		int pr = (backet_l - 1) * BACKET + BACKET; pr = min(pr, N);
		for (int i = pl; i < pr; i++) sub[0] += S[0][i];
		for (int i = pl; i < pr; i++) sub[1] += S[1][i];
		for (int i = pl; i < pr; i++) sub[2] += S[2][i];
		for (int i = pl; i < pr; i++) S[0][i] = sub[Orders[backet_l - 1][0]][i - pl];
		for (int i = pl; i < pr; i++) S[1][i] = sub[Orders[backet_l - 1][1]][i - pl];
		for (int i = pl; i < pr; i++) S[2][i] = sub[Orders[backet_l - 1][2]][i - pl];

		// Latter
		sub[0] = "";
		sub[1] = "";
		sub[2] = "";
		for (int i = cl; i < cr; i++) sub[0] += S[0][i];
		for (int i = cl; i < cr; i++) sub[1] += S[1][i];
		for (int i = cl; i < cr; i++) sub[2] += S[2][i];
		for (int i = cl; i < cr; i++) S[0][i] = sub[fst][i - cl];
		for (int i = cl; i < cr; i++) S[1][i] = sub[snd][i - cl];
		for (int i = cl; i < cr; i++) S[2][i] = sub[srd][i - cl];
	}

	else {
		// First Update
		if (true) {
			string sub[3] = {"", "", ""};
			int pl = (backet_l - 1) * BACKET;
			int pr = (backet_l - 1) * BACKET + BACKET;
			pr = min(pr, N);
			for (int i = pl; i < pr; i++) sub[0] += S[0][i];
			for (int i = pl; i < pr; i++) sub[1] += S[1][i];
			for (int i = pl; i < pr; i++) sub[2] += S[2][i];
			for (int i = pl; i < pr; i++) S[0][i] = sub[Orders[backet_l - 1][0]][i - pl];
			for (int i = pl; i < pr; i++) S[1][i] = sub[Orders[backet_l - 1][1]][i - pl];
			for (int i = pl; i < pr; i++) S[2][i] = sub[Orders[backet_l - 1][2]][i - pl];

			// Latter
			sub[0] = "";
			sub[1] = "";
			sub[2] = "";
			for (int i = cl; i < pr; i++) sub[0] += S[0][i];
			for (int i = cl; i < pr; i++) sub[1] += S[1][i];
			for (int i = cl; i < pr; i++) sub[2] += S[2][i];
			for (int i = cl; i < pr; i++) S[0][i] = sub[fst][i - cl];
			for (int i = cl; i < pr; i++) S[1][i] = sub[snd][i - cl];
			for (int i = cl; i < pr; i++) S[2][i] = sub[srd][i - cl];
		}

		// Last Update
		if (true) {
			string sub[3] = {"", "", ""};
			int pl = (backet_r + 0) * BACKET;
			int pr = (backet_r + 0) * BACKET + BACKET;
			pr = min(pr, N);
			for (int i = pl; i < pr; i++) sub[0] += S[0][i];
			for (int i = pl; i < pr; i++) sub[1] += S[1][i];
			for (int i = pl; i < pr; i++) sub[2] += S[2][i];
			for (int i = pl; i < pr; i++) S[0][i] = sub[Orders[backet_l - 1][0]][i - pl];
			for (int i = pl; i < pr; i++) S[1][i] = sub[Orders[backet_l - 1][1]][i - pl];
			for (int i = pl; i < pr; i++) S[2][i] = sub[Orders[backet_l - 1][2]][i - pl];

			// Latter
			sub[0] = "";
			sub[1] = "";
			sub[2] = "";
			for (int i = pl; i < cr; i++) sub[0] += S[0][i];
			for (int i = pl; i < cr; i++) sub[1] += S[1][i];
			for (int i = pl; i < cr; i++) sub[2] += S[2][i];
			for (int i = pl; i < cr; i++) S[0][i] = sub[fst][i - pl];
			for (int i = pl; i < cr; i++) S[1][i] = sub[snd][i - pl];
			for (int i = pl; i < cr; i++) S[2][i] = sub[srd][i - pl];
		}
	}

	// Final
	vector<int> tmp = {backet_l - 1, backet_r};
	sort(tmp.begin(), tmp.end());
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
	for (int idx : tmp) {
		Lexico[idx][0][1] = Compare(idx, 0, 1);
		Lexico[idx][1][2] = Compare(idx, 1, 2);
		Lexico[idx][2][0] = Compare(idx, 2, 0);
		Lexico[idx][1][0] = Compare(idx, 1, 0);
		Lexico[idx][2][1] = Compare(idx, 2, 1);
		Lexico[idx][0][2] = Compare(idx, 0, 2);
		Orders[idx][0] = 0;
		Orders[idx][1] = 1;
		Orders[idx][2] = 2;
	}
}


// ======================================================================== Main Function
int main() {
	// Step 1. Input
	cin >> N >> Q;
	for (int i = 0; i < 3; i++) cin >> S[i];
	for (int i = 0; i < Q; i++) cin >> L[i] >> R[i];
	for (int i = 0; i < Q; i++) L[i] -= 1;
	for (int i = 0; i < Q; i++) R[i] -= 1;

	// Step 2. Initialize
	for (int i = 0; i < N; i += BACKET) Orders[i / BACKET][0] = 0;
	for (int i = 0; i < N; i += BACKET) Orders[i / BACKET][1] = 1;
	for (int i = 0; i < N; i += BACKET) Orders[i / BACKET][2] = 2;
	for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][0][1] = Compare(i / BACKET, 0, 1);
	for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][1][2] = Compare(i / BACKET, 1, 2);
	for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][2][0] = Compare(i / BACKET, 2, 0);
	for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][1][0] = Compare(i / BACKET, 1, 0);
	for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][2][1] = Compare(i / BACKET, 2, 1);
	for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][0][2] = Compare(i / BACKET, 0, 2);

	// Step 3. Solve
	for (int i = 0; i < Q; i++) {
		pair<int, int> score[3];
		int v1 = FastCompare(L[i], R[i] + 1, 0, 1);
		int v2 = FastCompare(L[i], R[i] + 1, 1, 2);
		int v3 = FastCompare(L[i], R[i] + 1, 2, 0);
		score[0].second = 0;
		score[1].second = 1;
		score[2].second = 2;
		score[0].first += v1; score[1].first -= v1;
		score[1].first += v2; score[2].first -= v2;
		score[2].first += v3; score[0].first -= v3;

		// Sorting
		sort(score, score + 3);

		// Update
		Update(L[i], R[i] + 1, score[0].second, score[1].second, score[2].second);
	}

	// Output
	string ans[3] = {"", "", ""};
	for (int i = 0; i < N; i += BACKET) {
		string sub[3] = {"", "", ""};
		int cl = i;
		int cr = i + BACKET; cr = min(cr, N);
		for (int j = cl; j < cr; j++) sub[0] += S[0][j];
		for (int j = cl; j < cr; j++) sub[1] += S[1][j];
		for (int j = cl; j < cr; j++) sub[2] += S[2][j];
		ans[0] += sub[Orders[i / BACKET][0]];
		ans[1] += sub[Orders[i / BACKET][1]];
		ans[2] += sub[Orders[i / BACKET][2]];
	}
	cout << ans[0] << endl;
	cout << ans[1] << endl;
	cout << ans[2] << endl;
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 2
icpca
siaja
karta
2 4
1 5

output:

iarta
kiaja
scpca

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 9760kb

input:

6 6
aabbcc
bcacab
cbcaba
1 1
2 2
3 3
4 4
5 5
6 6

output:

aaaaaa
bbbbbb
cccccc

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 9764kb

input:

3 1
aba
aab
aac
1 3

output:

aab
aac
aba

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 1ms
memory: 9700kb

input:

1 1
z
y
x
1 1

output:

x
y
z

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 1300ms
memory: 10360kb

input:

100000 100000
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

result:

ok 3 lines

Test #6:

score: -100
Wrong Answer
time: 1152ms
memory: 10264kb

input:

100000 100000
ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttottttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:

ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttotttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttqtttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttkttttttttttttttttttttttttttttttttttttttttttttttt...

result:

wrong answer 1st lines differ - expected: 'tttttttttttttttttttttttttttttt...ttttttttttttttttttttttttttttttt', found: 'tttttttttttttttttttttttttttttt...ttttttttttttttttttttttttttttttt'
English 繁體中文 简体中文

Server Time: 2024-12-05 06:42:06 | OpenSource Project