QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#464901 | #1131. Crossing | lmeowdn | 0 | 60ms | 28328kb | C++14 | 3.1kb | 2024-07-06 15:48:57 | 2024-07-06 15:48:58 |
Judging History
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%