QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#661019 | #5541. Substring Sort | temmie# | RE | 0ms | 3920kb | C++17 | 3.5kb | 2024-10-20 14:20:16 | 2024-10-20 14:20:22 |
Judging History
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