QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #340776 | #4394. Keyboard Warrior | crsfaa# | AC ✓ | 40ms | 10284kb | C++14 | 1.9kb | 2024-02-29 11:54:55 | 2024-02-29 11:54:56 |
Judging History
answer
#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mxn=2e5+5;
using ull=unsigned long long;
const ull up=23333333333333;
char s[mxn];
ull mul[mxn],pre[mxn];
int c0[mxn],l0[mxn],c[mxn],l[mxn];
ull get(int c,int l)
{
return c*up+l;
}
int main()
{
int T=read(),i;
for(i=mul[0]=1;i<=2e5;i++)
mul[i]=mul[i-1]*up;
while(T--)
{
int n=read(),m=read(),i,pree,cnt,pc=0;
bool fl=0;
scanf("%s",s+1);
pree=s[1],cnt=1;
for(i=2;i<=n;i++)
{
if(s[i]==pree) cnt++;
else
{
c0[++pc]=pree,l0[pc]=cnt;
pree=s[i],cnt=1;
}
}
c0[++pc]=pree,l0[pc]=cnt;
ull tt=0;
for(i=2;i<pc;i++)
tt+=mul[i-1]*get(c0[i],l0[i]);
// for(i=1;i<=pc;i++)
// cout<<char(c0[i])<<' '<<l0[i]<<endl;
cnt=0;
while(m--)
{
char ch[5];
scanf("%s",ch);
int x=read();
if(fl) continue;
if(!x) continue;
if(*ch=='-')
{
for(;x&&cnt;cnt--)
{
int mn=min(l[cnt],x);
l[cnt]-=mn,x-=mn;
pre[cnt]=pre[cnt-1]+get(c[cnt],l[cnt])*mul[cnt];
if(l[cnt]) break;
}
continue;
}
if(c[cnt]==*ch)
l[cnt]+=x;
else
l[++cnt]=x,c[cnt]=*ch;
pre[cnt]=pre[cnt-1]+get(c[cnt],l[cnt])*mul[cnt];
if(pc==1)
{
if(c[cnt]==c0[1]&&l[cnt]>=l0[1])
fl=1,puts("yes");
continue;
}
// for(i=1;i<=cnt;i++)
// cout<<char(c[i])<<','<<l[i]<<endl;
if(cnt>=pc&&c[cnt]==c0[pc]&&l[cnt]>=l0[pc]&&c[cnt-pc+1]==c0[1]&&l[cnt-pc+1]>=l0[1]&&tt*mul[cnt-pc+1]==pre[cnt-1]-pre[cnt-pc+1])
fl=1,puts("yes");
}
if(!fl) puts("no");
}
}
/*
1
13 1000
aaaaaaaaaabbb
a 6
a 3
- 100
a 6
a 2
- 3
a 4
a 1
b 1
b 1
- 2
b 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 40ms
memory: 10284kb
input:
9 6 6 iloveu i 1 l 1 o 1 v 1 e 1 u 0 6 10 imfive u 10 - 20 i 1 m 1 f 1 i 1 v 5 - 4 e 2 - 2 4 4 abab a 2 b 2 - 3 b 1 2 10 dz a 1000000000 b 1000000000 - 1000000000 d 1000000000 - 1000000000 d 1000000000 z 1000000000 c 1000000000 e 1000000000 - 111111111 5 7 abcab a 1 b 1 a 1 b 1 c 1 a 1 b 1 200000 20...
output:
no yes no yes yes yes yes no yes
result:
ok 9 lines