QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#809521	#9791. Intrusive Donkey	Afterlife^#	ML	0ms	3804kb	C++20	2.6kb	2024-12-11 15:41:17	2024-12-11 15:41:24

Judging History

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

[2024-12-11 15:41:24]
评测

测评结果：ML
用时：0ms
内存：3804kb

查看

[2024-12-11 15:41:17]
提交

answer

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

#define int long long

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

struct T{
    int l,r,ls,rs,sum;
    int tag;
}t[N*2+1];

int cnt;

void mul(int x,int v)
{
    t[x].sum*=v;
    t[x].tag*=v;
}

void pushdown(int x)
{
    if(t[x].tag!=1)
    {
        mul(t[x].ls,t[x].tag);
        mul(t[x].rs,t[x].tag);
        t[x].tag=1;
    }
}

void update(int x)
{
    t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
}

int build(int l,int r)
{
    int x=++cnt;
    t[x].l=l,t[x].r=r;
    t[x].tag=1;
    if(l==r)
    {
        t[x].sum=1;
        return x;
    }
    int mid=(l+r)>>1;
    t[x].ls=build(l,mid);
    t[x].rs=build(mid+1,r);
    update(x);
    return x;
}

void Add(int x,int p,int v)
{
    if(t[x].l==t[x].r)
    {
        t[x].sum+=v;
        return;
    }
    int mid=(t[x].l+t[x].r)>>1;
    pushdown(x);
    if(p<=mid)
        Add(t[x].ls,p,v);
    else
        Add(t[x].rs,p,v);
    update(x);
}

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

int qpos(int x,int &k)
{
    if(t[x].sum<k)
    {
        k-=t[x].sum;
        return -1;
    }
    if(t[x].l==t[x].r)
        return t[x].l;
    int z=qpos(t[x].ls,k);
    if(z!=-1)
        return z;
    return qpos(t[x].rs,k);
}

int qsum(int x,int l,int r)
{
    if(l<=t[x].l&&t[x].r<=r)
        return t[x].sum;
    int mid=(t[x].l+t[x].r)>>1;
    pushdown(x);
    int ret=0;
    if(l<=mid)
        ret+=qsum(t[x].ls,l,r);
    if(r>mid)
        ret+=qsum(t[x].rs,l,r);
    return ret;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    build(1,n);
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int l,r;
            cin>>l>>r;
            int L=l,R=r;
            int x=qpos(1,L),y=qpos(1,R);
            if(x==y)
            {
                Add(1,x,r-l+1);
            }
            else
            {
                int ax=qsum(1,1,x)-l+1;
                int ay=r-qsum(1,1,y-1);
                if(l+1<=r-1)
                    Mul(1,l+1,r-1,2);
                Add(1,x,ax);
                Add(1,y,ay);
            }
        }
        else
        {
            int x;
            cin>>x;
            int p=qpos(1,x);
            cout<<s[p-1]<<"\n";
        }
    }
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3580kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3544kb

input:

output:

k
h

result:

ok 2 lines

Test #3:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #4:

score: 0

Accepted

time: 0ms

memory: 3604kb

input:

output:

k
h

result:

ok 2 lines

Test #5:

score: -100

Memory Limit Exceeded

input:

3 55
vfe
1 2 3
1 2 2
1 3 5
2 4
1 1 2
2 9
2 7
2 5
1 10 10
1 1 1
2 9
1 8 12
2 8
1 7 10
2 1
1 5 6
1 1 4
1 20 24
1 14 32
1 19 38
2 48
1 56 64
2 58
2 19
1 64 72
1 36 86
2 11
1 117 124
2 38
2 108
2 85
1 112 118
2 153
2 40
2 114
2 80
1 11 18
2 27
2 73
1 159 162
2 84
1 130 164
2 163
2 65
1 150 156
1 101 109...