QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#464901#1131. Crossinglmeowdn0 60ms28328kbC++143.1kb2024-07-06 15:48:572024-07-06 15:48:58

Judging History

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

  • [2024-07-06 15:48:58]
  • 评测
  • 测评结果:0
  • 用时:60ms
  • 内存:28328kb
  • [2024-07-06 15:48:57]
  • 提交

answer

//Shirasu Azusa 2024.7
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;  
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const int N=2e5+5,mod=1e9+7,B=3;
int n,m,a[15][N],tot,len[N],b[N],h[15][N],g[3][N],c[N];
char s[3][N],t[N],op[3];

int trans(char c) {
if(c=='J') return 0;
else if(c=='O') return 1;
else return 2;
}
int get(int x,int y) {
  if(x==y) return x;
  else return 3-x-y;
}
void cross(int *a,int *b,int *c) {
  rep(i,1,n) c[i]=get(a[i],b[i]);
}

namespace SegT{
  #define ls (p<<1)
  #define rs (p<<1|1)
  int len[N<<2],f[N<<2],tag[N<<2];
  int qry() {return f[1];}
  void cov(int p,int x) {f[p]=g[x][len[p]],tag[p]=x; return;}
  void psd(int p) {if(tag[p]!=-1) cov(ls,tag[p]),cov(rs,tag[p]),tag[p]=-1;}
  void build(int p,int l,int r) {
    len[p]=r-l+1; tag[p]=-1; if(l==r) {f[p]=c[l];return;} int mid=l+r>>1;
    build(ls,l,mid),build(rs,mid+1,r);  f[p]=(f[ls]*b[len[rs]]+f[rs])%mod;
  }
  void mdf(int p,int l,int r,int x,int y,int z) {
    if(l==x&&r==y) {cov(p,z); return;} int mid=l+r>>1; psd(p);
    if(y<=mid) mdf(ls,l,mid,x,y,z); else if(x>mid) mdf(rs,mid+1,r,x,y,z);
    else mdf(ls,l,mid,x,mid,z), mdf(rs,mid+1,r,mid+1,y,z);
    f[p]=(f[ls]*b[len[rs]]+f[rs])%mod;
  }
  void query() {
    bool ans=0;
    rep(x,0,8) ans|=(qry()==h[x][n]);
    puts(ans?"Yes":"No");
  }
}


signed main() {
  scanf("%lld%s%s%s",&n,s[0]+1,s[1]+1,s[2]+1);
  rep(i,1,n) a[0][i]=trans(s[0][i]);
  rep(i,1,n) a[1][i]=trans(s[1][i]);
  rep(i,1,n) a[2][i]=trans(s[2][i]);
  cross(a[0],a[1],a[3]);
  cross(a[1],a[2],a[4]);
  cross(a[2],a[0],a[5]);
  cross(a[3],a[4],a[6]);
  cross(a[4],a[5],a[7]);
  cross(a[5],a[3],a[8]);
  scanf("%lld%s",&m,t+1);
  rep(i,1,n) c[i]=trans(t[i]);
  rep(x,0,8) {
    rep(i,1,n) h[x][i]=(h[x][i-1]*B+a[x][i])%mod;
  }
  b[0]=1; rep(i,1,n) b[i]=b[i-1]*B%mod;
  rep(x,0,2) {
    rep(i,1,n) g[x][i]=(g[x][i-1]*B+x)%mod;
  }
  SegT::build(1,1,n);
  SegT::query();
  rep(i,1,m) {
    int l,r; scanf("%lld%lld%s",&l,&r,op);
    int z=trans(op[0]);
    SegT::mdf(1,1,n,l,r,z);
    SegT::query();
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 3
Accepted
time: 48ms
memory: 26344kb

input:

80
JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ
JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ
JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ
185606
IIJJOJIOJOIJIJJJJIOOJIIIIIIJIOIIOJOIJOIJOIJOJOI...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 185607 lines

Test #2:

score: 0
Accepted
time: 40ms
memory: 26244kb

input:

100
OOIJOIJIIOOIOIJIJOOIIIJIIOJOJIJOJIOIJJIOJOOIOJOOIIOIOJOJIJJJJIOOIJOIOJIJOOIJOOJOJJJIIOIIIIJIOJJJOIOI
OOIJOIJIIOOIOIJIJOOIIIJIIOJOJIJOJIOIJJIOJOOIOJOOIIOIOJOJIJJJJIOOIJOIOJIJOOIJOOJOJJJIIOIIIIJIOJJJOIOI
OOIJOIJIIOOIOIJIJOOIIIJIIOJOJIJOJIOIJJIOJOOIOJOOIIOIOJOJIJJJJIOOIJOIOJIJOOIJOOJOJJJIIOIIIIJIOJ...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 200001 lines

Test #3:

score: 0
Accepted
time: 42ms
memory: 28328kb

input:

100
OIIJJJIIJIOJJJIIOIJIIOIJOOIJIJJJOJIIIIIOJJIIJJOOJIJIIIOOIIOJIIJOJIIJOJIJIJOOIIOIJIIJIIOOIIIOIJIOJJOO
OIIJJJIIJIOJJJIIOIJIIOIJOOIJIJJJOJIIIIIOJJIIJJOOJIJIIIOOIIOJIIJOJIIJOJIJIJOOIIOIJIIJIIOOIIIOIJIOJJOO
OIIJJJIIJIOJJJIIOIJIIOIJOOIJIJJJOJIIIIIOJJIIJJOOJIJIIIOOIIOJIIJOJIIJOJIJIJOOIIOIJIIJIIOOIIIOIJ...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 200001 lines

Test #4:

score: 0
Accepted
time: 36ms
memory: 26288kb

input:

97
OOOIIIJOIOOOIJIIJIIJJOJJJOIJIJIIJOOOOJOJJOJIIIOIIJIJJOJOOJJOIOIOOJOOOJJJOIIIOIIJJIJOJIJIIJJIIIOII
OOOIIIJOIOOOIJIIJIIJJOJJJOIJIJIIJOOOOJOJJOJIIIOIIJIJJOJOOJJOIOIOOJOOOJJJOIIIOIIJJIJOJIJIIJJIIIOII
OOOIIIJOIOOOIJIIJIIJJOJJJOIJIJIIJOOOOJOJJOJIIIOIIJIJJOJOOJJOIOIOOJOOOJJJOIIIOIIJJIJOJIJIIJJIIIOII
194...

output:

Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 194162 lines

Test #5:

score: 0
Accepted
time: 36ms
memory: 26208kb

input:

91
JOIIOJJJOOIJJJJIJOJIIOJOJOIOIOIJJIIOJIOIJJOIJJOOIIOJIOJIJOOIIIIOOOJIJOIOIJIOJOIJOJOJOOIIJIO
JOIIOJJJOOIJJJJIJOJIIOJOJOIOIOIJJIIOJIOIJJOIJJOOIIOJIOJIJOOIIIIOOOJIJOIOIJIOJOIJOJOJOOIIJIO
JOIIOJJJOOIJJJJIJOJIIOJOJOIOIOIJJIIOJIOIJJOIJJOOIIOJIOJIJOOIIIIOOOJIJOIOIJIOJOIJOJOJOOIIJIO
193144
JOIIOJJJOOIJJJ...

output:

Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 193145 lines

Test #6:

score: 0
Accepted
time: 41ms
memory: 26272kb

input:

96
JIOIIOOJOOOIOOOJIJIIIIIIJIJIJJIIJOJJIOOIOJOOIOIJJIJOJOOOOJIOJOIIOOJJJOJIJOJJJIJJIIJJIIIIOJOJIOIJ
JIOIIOOJOOOIOOOJIJIIIIIIJIJIJJIIJOJJIOOIOJOOIOIJJIJOJOOOOJIOJOIIOOJJJOJIJOJJJIJJIIJJIIIIOJOJIOIJ
JIOIIOOJOOOIOOOJIJIIIIIIJIJIJJIIJOJJIOOIOJOOIOIJJIJOJOOOOJIOJOIIOOJJJOJIJOJJJIJJIIJJIIIIOJOJIOIJ
189200...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No...

result:

ok 189201 lines

Test #7:

score: 0
Accepted
time: 41ms
memory: 26340kb

input:

75
IIJOJIJIOOIOJOIIIJIOIIJIOIIJJJJOIJIJIOOJOOJJIIJOIJOOIIIJOIOJJJOIIIIIOJOIIIJ
IIJOJIJIOOIOJOIIIJIOIIJIOIIJJJJOIJIJIOOJOOJJIIJOIJOOIIIJOIOJJJOIIIIIOJOIIIJ
IIJOJIJIOOIOJOIIIJIOIIJIOIIJJJJOIJIJIOOJOOJJIIJOIJOOIIIJOIOJJJOIIIIIOJOIIIJ
197529
JJIOIJIJOOJOIOJJJIJOJJIJOJJIIIIOJIJIJOOIOOIIJJIOJIOOJJJIOJOIII...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 197530 lines

Test #8:

score: 0
Accepted
time: 42ms
memory: 26536kb

input:

100
OOIOJJIIOJJOOOOIIIIJIJIOIIIOJIOJJIOOJIIIJIJOOOJJJOIIJIIOOOOJIIJOIIJIOJJIJIOOOJIOJJJOIOOOJOJJJOOIJOJO
OOIOJJIIOJJOOOOIIIIJIJIOIIIOJIOJJIOOJIIIJIJOOOJJJOIIJIIOOOOJIIJOIIJIOJJIJIOOOJIOJJJOIOOOJOJJJOOIJOJO
OOIOJJIIOJJOOOOIIIIJIJIOIIIOJIOJJIOOJIIIJIJOOOJJJOIIJIIOOOOJIIJOIIJIOJJIJIOOOJIOJJJOIOOOJOJJJO...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No...

result:

ok 200001 lines

Test #9:

score: 0
Accepted
time: 39ms
memory: 28288kb

input:

100
IJIIIOOIOIIIOOOIOJJJJOIOJIOIOOJOIJJOJJOIJJOJIIIJOJJIJIIJIIJJOOOOIJOJIOOJOOOJOOOJOIJIOOOIIOIIJOOJJJJO
IJIIIOOIOIIIOOOIOJJJJOIOJIOIOOJOIJJOJJOIJJOJIIIJOJJIJIIJIIJJOOOOIJOJIOOJOOOJOOOJOIJIOOOIIOIIJOOJJJJO
IJIIIOOIOIIIOOOIOJJJJOIOJIOIOOJOIJJOJJOIJJOJIIIJOJJIJIIJIIJJOOOOIJOJIOOJOOOJOOOJOIJIOOOIIOIIJO...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No...

result:

ok 200001 lines

Test #10:

score: -3
Wrong Answer
time: 60ms
memory: 24524kb

input:

100
IIJOIIOIIIIOOOIOOJIIIOIIOOIJOJIJJOOJJJOOIOOOIOJIIJIIOIJIJOOJIOJOOJJIIOIIOJOOJIIIJJJOOOOIOIOJJIIIOOIO
IIJOIIOIIIIOOOIOOJIIIOIIOOIJOJIJJOOJJJOOIOOOIOJIIJIIOIJIJOOJIOJOOJJIIOIIOJOOJIIIJJJOOOOIOIOJJIIIOOIO
IIJOIIOIIIIOOOIOOJIIIOIIOOIJOJIJJOOJJJOOIOOOIOJIIJIIOIJIJOOJIOJOOJJIIOIIOJOOJIIIJJJOOOOIOIOJJI...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

wrong answer 438th lines differ - expected: 'No', found: 'Yes'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%