Submission #661613

#	Time	Username	Problem	Language	Result	Execution time	Memory
661613		alvingogo	Crossing (JOI21_crossing)	C++14	100 / 100	1483 ms	33568 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int chg(char a){
    if(a=='J'){
        return 0;
    }
    if(a=='O'){
        return 1;
    }
    if(a=='I'){
        return 2;
    }
}
vector<int> get(vector<int> a,vector<int> b){
    int n=a.size();
    vector<int> c(n);
    for(int i=0;i<n;i++){
        c[i]=(2*a[i]+2*b[i])%3;
    }
    return c;
}
vector<int> g;
struct ST{
    struct no{
        int x=0,xx=0,sum=0;
        int sz=0;
        int tag=-1;
    };
    int z=0;
    vector<no> st;
    void init(int x){
        st.resize(4*x);
    }
    void build(int v,int L,int R){
        if(L==R){
            st[v].sum=g[L];
            st[v].sz=1;
            z+=g[L]*g[L];
            return;
        }
        int m=(L+R)/2;
        build(2*v+1,L,m);
        build(2*v+2,m+1,R);
        st[v].sz=st[2*v+1].sz+st[2*v+2].sz;
        st[v].sum=st[2*v+1].sum+st[2*v+2].sum;
    }
    void pull(int v){
        st[v].x=st[2*v+1].x+st[2*v+2].x;
        st[v].xx=st[2*v+1].xx+st[2*v+2].xx;
    }
    void upd(int v,int x){
        st[v].tag=x;
        st[v].xx=st[v].sz*x*x;
        st[v].x=st[v].sum*x;
    }
    void pudo(int v){
        if(st[v].tag==-1){
            return;
        }
        upd(2*v+1,st[v].tag);
        upd(2*v+2,st[v].tag);
        st[v].tag=-1;
    }
    void update(int v,int L,int R,int l,int r,int k){
        if(l==L && r==R){
            upd(v,k);
            return;
        }
        int m=(L+R)/2;
        pudo(v);
        if(r<=m){
            update(2*v+1,L,m,l,r,k);
        }
        else if(l>m){
            update(2*v+2,m+1,R,l,r,k);
        }
        else{
            update(2*v+1,L,m,l,m,k);
            update(2*v+2,m+1,R,m+1,r,k);
        }
        pull(v);
    }
    bool query(){
        return (st[0].xx-2*st[0].x+z)==0;
    }
};
int main(){
    AquA;
    int n;
    cin >> n;
    string a,b,c;
    cin >> a >> b >> c;
    vector<vector<int> > v(3,vector<int>(n));
    for(int i=0;i<n;i++){
        v[0][i]=chg(a[i]);
        v[1][i]=chg(b[i]);
        v[2][i]=chg(c[i]);
    }
    v.push_back(get(v[0],v[1]));
    v.push_back(get(v[1],v[2]));
    v.push_back(get(v[0],v[2]));
    v.push_back(get(v[3],v[2]));
    v.push_back(get(v[4],v[0]));
    v.push_back(get(v[5],v[1]));
    int q;
    cin >> q;
    string t;
    cin >> t;
    vector<int> p(n);
    for(int i=0;i<n;i++){
        p[i]=chg(t[i]);
    }
    vector<pair<pair<int,int>,int> > vq(q);
    for(int i=0;i<q;i++){
        cin >> vq[i].fs.fs >> vq[i].fs.sc;
        char c;
        cin >> c;
        vq[i].sc=chg(c);
    }
    vector<int> ans(q+1);
    for(int i=0;i<9;i++){
        g=v[i];
        ST st;
        st.init(n);
        st.build(0,0,n-1);
        for(int j=0;j<n;j++){
            st.update(0,0,n-1,j,j,p[j]);
        }
        ans[0]|=st.query();
        for(int j=0;j<q;j++){
            st.update(0,0,n-1,vq[j].fs.fs-1,vq[j].fs.sc-1,vq[j].sc);
            ans[j+1]|=st.query();
        }
    }
    for(int i=0;i<=q;i++){
        if(ans[i]){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int chg(char)':
Main.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
   19 | }
      | ^

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