Submission #1013904

#TimeUsernameProblemLanguageResultExecution timeMemory
1013904BaytoroCrossing (JOI21_crossing)C++17
100 / 100
2048 ms90420 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
//#define int ll
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
struct node {
    int ok;
    char c;
};
struct segtree {
    vector<node> tree;
    vector<int> lazy;
    node combine(node a, node b) {
        node res={0,'x'};

        res.ok=a.ok&b.ok;

        if(a.c=='x' || b.c=='x' || a.c!=b.c) res.c='x';
        else res.c=a.c;

        return res;
    }
    void build(int x, int l, int r, string &a, string &b) {
        if(l==r) {
            if(a[l]==b[l])
                tree[x].ok=1;
            else
                tree[x].ok=0;
            tree[x].c=a[l];
            return;
        }
        int md=(l+r)/2;
        build(2*x,l,md,a,b);
        build(2*x+1,md+1,r,a,b);

        tree[x]=combine(tree[2*x],tree[2*x+1]);
    }
    void init(int x, string a, string b) {
        tree.resize(x*4);
        lazy.assign(x*4,-1);
        build(1,0,x-1,a,b);
    }
    void push(int x,int l, int r) {
        if(tree[x].c==lazy[x])
            tree[x].ok=1;
        else
            tree[x].ok=0;
        if(2*x+1<tree.size()) {
            lazy[2*x]=lazy[x];
            lazy[2*x+1]=lazy[x];
        }
        lazy[x]=-1;
    }
    void update(int lx, int rx, char c, int x, int l, int r) {
        if(lazy[x]!=-1) {
            push(x,l,r);
        }
        if(l>rx || r<lx) return;
        if(lx<=l && r<=rx) {
            lazy[x]=c;
            push(x,l,r);
            return;
        }

        int md=(l+r)/2;


        update(lx,rx,c,2*x,l,md);
        update(lx,rx,c,2*x+1,md+1,r);

        tree[x]=combine(tree[2*x],tree[2*x+1]);

    }
    bool get() {
        return tree[1].ok;
    }
};
string comb(string a, string b) {
    for(int i=0;i<a.size();i++) {
        if(a[i]==b[i]) continue;
        if('J'!=a[i] && 'J'!=b[i]) a[i]='J';
        else if('O'!=a[i] && 'O'!=b[i]) a[i]='O';
        else if('I'!=a[i] && 'I'!=b[i]) a[i]='I';
    }
    return a;
}
void solve() {
    int n;cin>>n;
    string a,b,c;cin>>a>>b>>c;
    int q;cin>>q;
    string s;cin>>s;
    vector<segtree> st(9);
    st[0].init(n,a,s); //cout<<a<<endl;
    st[1].init(n,b,s); //cout<<b<<endl;
    st[2].init(n,c,s); //cout<<c<<endl;

    st[3].init(n,comb(a,b),s); //cout<<comb(a,b)<<endl;
    st[4].init(n,comb(a,c),s); //cout<<comb(a,c)<<endl;
    st[5].init(n,comb(b,c),s); //cout<<comb(b,c)<<endl;

    st[6].init(n,comb(comb(a,b),c),s); //cout<<comb(comb(a,b),c)<<endl;
    st[7].init(n,comb(comb(c,b),a),s); //cout<<comb(comb(c,b),a)<<endl;
    st[8].init(n,comb(comb(a,c),b),s); //cout<<comb(comb(a,c),b)<<endl;
    //st.init(n,a,s);
    bool ans=0;
    for(int i=0;i<9;i++) ans|=st[i].get();
    cout<<(ans?"Yes":"No")<<endl;

    while(q--) {
        int l, r;cin>>l>>r;l--,r--;
        char c;cin>>c;
        ans=0;
        for(int i=0;i<9;i++)
            st[i].update(l,r,c,1,0,n-1);
        for(int i=0;i<9;i++)
            ans|=st[i].get();
        cout<<(ans?"Yes":"No")<<endl;
    }
}
signed main(){
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}
//#endif

Compilation message (stderr)

Main.cpp: In member function 'void segtree::push(int, int, int)':
Main.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if(2*x+1<tree.size()) {
      |            ~~~~~^~~~~~~~~~~~
Main.cpp: In function 'std::string comb(std::string, std::string)':
Main.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<a.size();i++) {
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...