QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354600#5541. Substring SortSolitaryDream#TL 1ms5660kbC++142.6kb2024-03-15 18:30:592024-03-15 18:31:00

Judging History

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

  • [2024-03-15 18:31:00]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5660kb
  • [2024-03-15 18:30:59]
  • 提交

answer

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

#define int long long

const int N=1e5+1e3+7;

const int P=(1ll<<61)-1,bs=13131;

string s[3];

int n;

int pw[N];

int add(int a,int b)
{
    return a+b>=P?a+b-P:a+b;
}

int mul(int a,int b)
{
    return (__int128)a*b%P;
}

struct T{
    int l,r,ls,rs,sz;
    array<int,3> ha,tag;
}t[N*2+1];

void update(int x)
{
    for(int i=0;i<3;i++)
        t[x].ha[i]=add(mul(t[t[x].ls].ha[i],pw[t[t[x].rs].sz]),t[t[x].rs].ha[i]);
}

void app(int x,array<int,3> v)
{
    array<int,3> nh,nt;
    for(int i=0;i<3;i++)
        nh[i]=t[x].ha[v[i]],nt[i]=t[x].tag[v[i]];
    t[x].ha=nh,t[x].tag=nt;
}

void pushdown(int x)
{
    app(t[x].ls,t[x].tag);
    app(t[x].rs,t[x].tag);
    for(int i=0;i<3;i++)
        t[x].tag[i]=i;
}

int cnt;

int build(int l,int r)
{
    int x=++cnt;
    t[x].l=l,t[x].r=r;
    for(int i=0;i<3;i++)
        t[x].tag[i]=i;
    t[x].sz=r-l+1;
    if(l==r)
    {
        for(int i=0;i<3;i++)
            t[x].ha[i]=s[i][l];
        return x;
    }
    int mid=(l+r)>>1;
    t[x].ls=build(l,mid);
    t[x].rs=build(mid+1,r);
    update(x);
    return x;
}

int cmpt(int x,int l,int r,int u,int v)
{
    if(l<=t[x].l&&t[x].r<=r)
    {
        if(t[x].ha[u]==t[x].ha[v])
            return 0;
        if(t[x].l==t[x].r)
            return t[x].ha[u]<t[x].ha[v]?-1:1;
    }
    pushdown(x);
    int mid=(t[x].l+t[x].r)>>1;
    int ret=0;
    if(l<=mid)
        ret=cmpt(t[x].ls,l,r,u,v);
    if(ret)
        return ret;
    return cmpt(t[x].rs,l,r,u,v);
}

void change(int x,int l,int r,array<int,3> v)
{
    if(l<=t[x].l&&t[x].r<=r)
    {
        app(x,v);
        return;
    }
    int mid=(t[x].l+t[x].r)>>1;
    pushdown(x);
    if(l<=mid)
        change(t[x].ls,l,r,v);
    if(r>mid)
        change(t[x].rs,l,r,v);
    update(x);
}

int L,R;

bool cmp(int u,int v)
{
    return cmpt(1,L,R,u,v)==-1;
}

void dfs(int u,int x)
{
    if(t[x].l==t[x].r)
    {
        cout<<(char)t[x].ha[u];
        return;
    }
    pushdown(x);
    dfs(u,t[x].ls);
    dfs(u,t[x].rs);
}

int q;

signed main()
{
    cin>>n>>q;
    pw[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=mul(pw[i-1],bs);
    for(int i=0;i<3;i++)
    {
        cin>>s[i];
        s[i]=' '+s[i];
    }
    build(1,n);
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        array<int,3> f;
        iota(f.begin(),f.end(),0);
        L=l,R=r;
        sort(f.begin(),f.end(),cmp);
        change(1,l,r,f);
    }
    for(int i=0;i<3;i++)
        dfs(i,1),cout<<"\n";
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5660kb

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: 3632kb

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: 5576kb

input:

3 1
aba
aab
aac
1 3

output:

aab
aac
aba

result:

ok 3 lines

Test #4:

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

input:

1 1
z
y
x
1 1

output:

x
y
z

result:

ok 3 lines

Test #5:

score: -100
Time Limit Exceeded

input:

100000 100000
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:


result: