Submission #938338

#	Time	Username	Problem	Language	Result	Execution time	Memory
938338		carriewang	Crossing (JOI21_crossing)	C++17	100 / 100	1068 ms	28320 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
const int maxn=200005;
string sa,sb,sc,t;
int n,q,ql[maxn],qr[maxn],a[10][maxn],toi[100],st[1<<20],m[1<<20],lazy[1<<20],ans[maxn];
char c[maxn];
void pull(int x){
    if(lazy[x]==0) return;
    lazy[x<<1]=lazy[x<<1|1]=lazy[x];
    st[x]=(m[x]==lazy[x]);
    lazy[x]=0;
}
void build(int x,int i,int l,int r){
    if(l==r){
        m[x]=(1<<a[i][l]);
        st[x]=(a[i][l]==toi[t[l]]);
        lazy[x]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,i,l,mid);
    build(x<<1|1,i,mid+1,r);
    m[x]=m[x<<1]|m[x<<1|1];
    st[x]=st[x<<1]&st[x<<1|1];
    lazy[x]=0;
}
void update(int x,int l,int r,int ql,int qr,int val){
    if(ql<=l && r<=qr){
        lazy[x]=val;
        pull(x);
        return;
    }
    pull(x);
    int mid=(l+r)>>1;
    if(ql<=mid) update(x<<1,l,mid,ql,qr,val);
    if(qr>mid) update(x<<1|1,mid+1,r,ql,qr,val);
    pull(x<<1),pull(x<<1|1);
    st[x]=st[x<<1]&st[x<<1|1];
}
void solve(int i){
    build(1,i,0,n-1);
    if(st[1]) ans[0]=1;
    for(int j=1;j<=q;j++){
        update(1,0,n-1,ql[j],qr[j],(1<<toi[c[j]]));
        if(st[1]) ans[j]=1;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    toi['J']=0,toi['O']=1,toi['I']=2;
    cin >> n;
    cin >> sa >> sb >> sc;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            int k=(7-i-j)%3;
            for(int l=0;l<n;l++){
                int sum=0;
                sum+=toi[sa[l]]*i;
                sum+=toi[sb[l]]*j;
                sum+=toi[sc[l]]*k;
                a[i*3+j][l]=sum%3;
            }
        }
    }
    cin >> q;
    cin >> t;
    for(int i=1;i<=q;i++){
        cin >> ql[i] >> qr[i] >> c[i];
        ql[i]--,qr[i]--;
    }
    for(int i=0;i<9;i++) solve(i);
    for(int i=0;i<=q;i++){
        cout << ((ans[i]==1) ? "Yes\n" : "No\n");
    }
}

Compilation message (stderr)

Main.cpp: In function 'void build(int, int, int, int)':
Main.cpp:24:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |         st[x]=(a[i][l]==toi[t[l]]);
      |                                 ^
Main.cpp: In function 'void solve(int)':
Main.cpp:52:47: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |         update(1,0,n-1,ql[j],qr[j],(1<<toi[c[j]]));
      |                                            ~~~^
Main.cpp: In function 'int main()':
Main.cpp:66:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   66 |                 sum+=toi[sa[l]]*i;
      |                               ^
Main.cpp:67:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   67 |                 sum+=toi[sb[l]]*j;
      |                               ^
Main.cpp:68:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   68 |                 sum+=toi[sc[l]]*k;
      |                               ^

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51