QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#801214	#9791. Intrusive Donkey	isWFnoya^#	WA	1ms	5964kb	C++20	3.0kb	2024-12-06 19:39:04	2024-12-06 19:39:09

Judging History

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

[2024-12-06 19:39:09]
评测

测评结果：WA
用时：1ms
内存：5964kb

查看

[2024-12-06 19:39:04]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1919810;
int n,m;
int a[N],pos[N];
char s[N];

typedef struct{
    int l,r;
    ll sum;
    ll tag;
}Node;

Node tr[N];
void pushup(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u){
    if(tr[u].tag!=1){
        tr[u<<1].sum*=tr[u].tag;tr[u<<1].tag*-tr[u].tag;
        tr[u<<1|1].sum*=tr[u].tag;tr[u<<1|1].tag*=tr[u].tag;
        tr[u].tag=1;
    }
}

void build(int u,int l,int r){
    tr[u]={l,r,0,1};
    if(l==r){
        tr[u].sum=1,tr[u].tag=1;
    }else{
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r,ll c){
    if(l>r) return;
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].sum*=c;
        tr[u].tag*=c;
    }else{
        int mid=tr[u].l+tr[u].r>>1;
        pushdown(u);
        if(l<=mid) modify(u<<1,l,r,c);
        if(r>mid) modify(u<<1|1,l,r,c);
        pushup(u);
    }
}

void modify_add(int u,int l,ll c){
    if(tr[u].l==l&&tr[u].r==l){
        tr[u].sum+=c;
        // tr[u].tag*=c;
    }else{
        int mid=tr[u].l+tr[u].r>>1;
        pushdown(u);
        if(l<=mid) modify_add(u<<1,l,c);
        else modify_add(u<<1|1,l,c);
        pushup(u);
    }
}

ll query_sum(int u,int l,int r){
    if(r==0) return 0;
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u].sum;
    }else{
        int mid=tr[u].l+tr[u].r>>1;
        ll tot=0;
        pushdown(u);
        if(l<=mid) tot+=query_sum(u<<1,l,r);
        if(r>mid) tot+=query_sum(u<<1|1,l,r);
        pushup(u);
        return tot;
    }
}

int query(int u,ll c,ll now){
    if(tr[u].l==tr[u].r){
        return tr[u].l;
    }else{
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        int ans=0;
        if(now+tr[u<<1].sum>=c) ans= query(u<<1,c,now);
        else ans=query(u<<1|1,c,now+tr[u<<1].sum);
        pushup(u);
        return ans;
    }
}
int main()
{
    cin>>n>>m;
    scanf("%s",s+1);
    build(1,1,n);
    while(m--){
        ll op,l,r;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld",&l,&r);
            int idl=query(1,l,0),idr=query(1,r,0);
            // cout<<idl<<" "<<idr<<endl;
            if(idl==idr){
                ll ad=(r-l+1);
                modify_add(1,idl,ad);
            }else{
                ll sum1=query_sum(1,1,idl),sum2=query_sum(1,1,idr-1);
                ll ad1=sum1-l+1,ad2=r-sum2;
                
                // ad1,ad2*=2;
                modify_add(1,idl,ad1);
                modify_add(1,idr,ad2);

                modify(1,idl+1,idr-1,2);
            }
        }else{
            scanf("%lld",&l);
            int id=query(1,l,0);
            // cout<<id<<endl;
            printf("%c\n",s[id]);
        }
        // for(int i=1;i<=n;i++) cout<<query_sum(1,i,i)<<" ";
        // cout<<endl;
    }
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 5884kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 1ms

memory: 5896kb

input:

output:

k
h

result:

ok 2 lines

Test #3:

score: 0

Accepted

time: 1ms

memory: 5900kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 5964kb

input:

output:

k
h

result:

ok 2 lines

Test #5:

score: 0

Accepted

time: 1ms

memory: 5960kb

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...

output:

f
e
f
f
f
f
v
f
e
f
f
f
e
e
e
f
e
e
f
e
e
e
f
e
f
e
v

result:

ok 27 lines

Test #6:

score: -100

Wrong Answer

time: 0ms

memory: 5900kb

input:

60 51
ranhfkbjhkxckkcbhgsspsjcbjgpwcfvmqqlvlfualndmqqsihsfdyqviowu
2 53
2 37
2 33
2 60
1 1 32
2 44
1 87 92
1 7 77
1 56 86
2 17
1 128 184
1 26 159
2 323
2 55
1 24 316
1 435 652
2 316
2 444
1 819 868
2 27
2 912
2 313
1 555 576
1 510 942
1 1118 1269
2 365
2 84
1 595 650
2 1468
2 258
1 1557 1607
2 938
1...

output:

d
v
m
u
j
k
u
s
l
i
k
u
m
f
g
u
f
u
k
u
u
u
u
u
u
u

result:

wrong answer 5th lines differ - expected: 's', found: 'j'