QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #774587 | #9791. Intrusive Donkey | ucup-team4770# | RE | 2ms | 9984kb | C++17 | 1.8kb | 2024-11-23 13:30:03 | 2024-11-23 13:30:03 |
Judging History
answer
//Date: 2024-11-23 13:21:59
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
bool MBE;
namespace SOLVER {
const int inf=2e18;
int n,q;char s[200005];
int mul(int x,int y) {return min(x*y,inf);}int add(int x,int y) {return min(x+y,inf);}
struct Segment_Tree {
int t[4*200005],l[4*200005],r[4*200005],laz[4*200005];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l[p]+r[p])>>1)
void pushdown(int p) {t[ls]=mul(t[ls],laz[p]),t[rs]=mul(t[rs],laz[p]),laz[ls]=mul(laz[ls],laz[p]),laz[rs]=mul(laz[rs],laz[p]),laz[p]=1;}
void build(int p,int L,int R) {
l[p]=L,r[p]=R,laz[p]=1;if(l[p]==r[p]) {t[p]=1;return;}
build(ls,L,mid);build(rs,mid+1,R);t[p]=add(t[ls],t[rs]);
}
void update(int p,int L,int R) {
if(L<=l[p]&&r[p]<=R) {t[p]=mul(t[p],2),laz[p]=mul(laz[p],2);return;}
pushdown(p);
if(L<=mid) update(ls,L,R);
if(R>mid) update(rs,L,R);
t[p]=add(t[ls],t[rs]);
}
int query(int p,int k) {
if(l[p]==r[p]) return l[p];pushdown(p);
if(t[ls]<k) return query(rs,k-t[rs]);else return query(ls,k);
}
} t;
void MAIN() {
scanf("%lld%lld%s",&n,&q,s+1);t.build(1,1,n);
while(q--) {
int op=rd(),l,r,x;
if(op==1) l=rd(),r=rd(),t.update(1,l,r);
else x=rd(),putchar(s[t.query(1,x)]),puts("");
}
}
}
bool MED;
signed main() {
//freopen(".in","r",stdin);freopen(".out","w",stdout);
for(int tt=1;tt;tt--) SOLVER::MAIN();
cerr<<(&MBE-&MED)/1024<<" KB, "<<1000*clock()/CLOCKS_PER_SEC<<" ms\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9828kb
input:
4 7 abac 2 2 2 3 1 2 3 2 3 2 4 2 5 2 6
output:
b a b a a c
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 9920kb
input:
5 4 shrek 1 1 2 2 7 1 1 7 2 7
output:
k h
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 9984kb
input:
4 7 abac 2 2 2 3 1 2 3 2 3 2 4 2 5 2 6
output:
b a b a a c
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 9892kb
input:
5 4 shrek 1 1 2 2 7 1 1 7 2 7
output:
k h
result:
ok 2 lines
Test #5:
score: -100
Runtime Error
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...