QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#661019#5541. Substring Sorttemmie#RE 0ms3920kbC++173.5kb2024-10-20 14:20:162024-10-20 14:20:22

Judging History

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

  • [2024-10-20 14:20:22]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3920kb
  • [2024-10-20 14:20:16]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define fastio ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

#ifdef LOCAL
#define cout cout << "\033[0;32m"
#define cerr cerr << "\033[0;31m"
#define endl "\n" << "\033[0m"
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
#define endl "\n"
#endif

const int MAX_N = 5e5+10;
const int INF = 2e18;
mt19937 seed(time(NULL));
inline int rnd(int l, int r){ return uniform_int_distribution(l, r)(seed); }
int A = rnd(100, 1e9+7);
const int B = 1e9+7;

// declare
int n, q;
vector<string> v;
int l, r;
vector<int> P;

struct Treap{
	Treap *l, *r;
	int pri, val, sz, sum;
	char c;

	Treap(int _val, int _c){
		l = nullptr;
		r = nullptr;
		pri = rnd(1, 1e9);
		val = sum = _val;
		sz = 1;
		c = _c;
	}
} *tr[3], *tr_l[3], *tr_r[3], *tr_mid[3], *tr_tmp, *tr_tmpx[4];

int size(Treap *a){
	return a ? a->sz : 0;
}

int sum(Treap *a){
	return a ? a->sum : 0;
}

void pull(Treap *t){
	t->sz = size(t->l)+size(t->r)+1;
	t->sum = (sum(t->l) + sum(t->r) + t->val) % B;
}

Treap *merg(Treap *a, Treap *b){
	if (!a || !b) return a ? a : b;

	if (a->pri > b->pri){
		a->r = merg(a->r, b);
		pull(a);
		return a;
	}else{
		b->l = merg(a, b->l);
		pull(b);
		return b;
	}
}

void split(Treap *&t, int k, Treap *&a, Treap *&b){
	if (!t) a = b = nullptr;
	else if (size(t->l)+1<=k){
		a = t;
		split(t->r, k-size(t->l)-1, a->r, b);
		pull(a);
	}else{
		b = t;
		split(t->l, k, a, b->l);
		pull(b);
	}
}

ostream & operator << (ostream &os, Treap *t){
	if (t==0) return os;
	os << t->l;
	os << t->c;
	os << t->r;
	return os;
}

void print(Treap *t){
	if (t->l!=0) print(t->l);
	cout << t->c;
	if (t->r!=0) print(t->r);
}

int pref(int i, int k) {
    split(tr_mid[i], k, tr_tmpx[0], tr_tmpx[1]);
    int ret = sum(tr_tmpx[0]);
    tr_mid[i] = merg(tr_tmpx[0], tr_tmpx[1]);
    return ret;
}

char treap_get(Treap *&t, int k){
	if (size(t->l) + 1 < k) {
		return treap_get(t->r, k-size(t->l)-1);
	} else if (k == size(t->l)+1) {
	    return t->c;
	} else {
		return treap_get(t->l, k);
	}
}

inline bool check_swap(int i, int j) {
	assert(tr_mid[i]);
	assert(tr_mid[j]);
    int ll = 1, rr = tr_mid[i]->sz+1, ans = 0;
    while (ll < rr) {
        int mid = ll+(rr-ll)/2;
        if (pref(i, mid)==pref(j, mid)) {
			ans = mid;
			ll = mid+1;
        }else{
			rr = mid;
		}
    }

	if (ans==tr_mid[i]->sz){
		return false;
	}else{
		return treap_get(tr_mid[i], ans+1)>treap_get(tr_mid[j], ans+1);
	}
}

inline void srt(int i, int j) {
    if (check_swap(i, j)) {
        swap(tr_mid[i], tr_mid[j]);
    }
}

void solve1(){

	// input
	cin >> n >> q;
	v.resize(n);
	for (int i=0 ; i<3 ; i++){
		cin >> v[i];
	}

	// process
	P.resize(n);
	P[0] = 1;
	for (int i=1 ; i<n ; i++){
		P[i] = P[i-1]*A%B;
	}
	vector<vector<int>> p(3, vector<int>(n));
	for (int i = 0 ; i < 3 ; i++) {
		for (int j = 0 ; j < n ; j++) {
			p[i][j] = P[j] * v[i][j] % B;
			tr[i] = merg(tr[i], new Treap(p[i][j], v[i][j]));
		}
	}

	// queries
	for (int cases = 0 ; cases < q; ++cases){
		cin >> l >> r;
		l--, r--;
		for (int j = 0; j < 3; ++j) {
			split(tr[j], l, tr_l[j], tr_tmp);
            split(tr_tmp, r - l + 1, tr_mid[j], tr_r[j]);
		}
        srt(0, 1);
        srt(0, 2);
        srt(1, 2);
		for (int j = 0; j < 3; ++j) {
            tr_tmp = merg(tr_l[j], tr_mid[j]);
            tr[j] = merg(tr_tmp, tr_r[j]);
		}
	}

	// output
	print(tr[0]);
	cout << endl;
	print(tr[1]);
	cout << endl;
	print(tr[2]);
	cout << endl;

	return;
}

signed main(){
	fastio;

	int t = 1;
	while (t--){
		solve1();
	}

	return 0;
}



詳細信息

Test #1:

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

input:

5 2
icpca
siaja
karta
2 4
1 5

output:

iarta
kiaja
scpca

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3628kb

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: 0ms
memory: 3904kb

input:

3 1
aba
aab
aac
1 3

output:

aab
aac
aba

result:

ok 3 lines

Test #4:

score: -100
Runtime Error

input:

1 1
z
y
x
1 1

output:


result: