Submission #1147741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147741		guagua0407	Crossing (JOI21_crossing)	C++20	100 / 100	509 ms	25840 KiB

Main

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int main() {_
    int n;
    cin>>n;
    vector<string> S(3);
    for(int i=0;i<3;i++){
        cin>>S[i];
    }
    function<string(int,int)> op=[&](int aa,int bb){
        string a=S[aa];
        string b=S[bb];
        string c;
        for(int i=0;i<n;i++){
            if(a[i]==b[i]){
                c+=a[i];
            }
            else{
                for(auto cc:{'J','O','I'}){
                    if(a[i]!=cc and b[i]!=cc){
                        c+=cc;
                        break;
                    }
                }
            }
        }
        return c;
    };
    S.push_back(op(0,1));
    S.push_back(op(1,2));
    S.push_back(op(2,0));
    S.push_back(op(3,2));
    S.push_back(op(4,0));
    S.push_back(op(5,1));
    vector<vector<pair<int,char>>> vec(9,vector<pair<int,char>>(n,{-1,'#'}));
    vector<int> ok(9);
    {
        for(int t=0;t<9;t++){
            int l=0;
            for(int r=1;r<n;r++){
                if(S[t][r-1]!=S[t][r]){
                    vec[t][l]={r-1,S[t][r-1]};
                    l=r;
                    ok[t]++;
                }
            }
            vec[t][l]={n-1,S[t][n-1]};
            ok[t]++;
        }
    }
    int q;
    cin>>q;
    struct node{
        int l,r;
        char c;
        node(){}
        node(int _l,int _r,char _c){
            l=_l;
            r=_r;
            c=_c;
        }
        bool operator<(const node &y)const{
            return l<y.l;
        }
    };
    set<node> seg;
    function<void(node,int)> mod2=[&](node v,int d){
        for(int i=0;i<9;i++){
            if(vec[i][v.l]==make_pair(v.r,v.c)){
                ok[i]-=d;
            }
        }
    };
    function<void(node,int)> mod=[&](node v,int d){
        if(d==1){
            auto it=seg.upper_bound(v);
            if(it!=seg.end()){
                node cur=(*it);
                if(cur.l==v.r+1 and cur.c==v.c){
                    seg.erase(it);
                    mod2(cur,-1);
                    v.r=cur.r;
                }
            }
            it=seg.upper_bound(v);
            if(!seg.empty() and it!=seg.begin()){
                it=prev(it);
                node cur=(*it);
                if(cur.r==v.l-1 and cur.c==v.c){
                    seg.erase(it);
                    mod2(cur,-1);
                    v.l=cur.l;
                }
            }
            seg.insert(v);
            mod2(v,1);
        }
        else{
            mod2(v,-1);
            seg.erase(v);
        }
    };
    function<void(string)> init=[&](string T){
        int l=0;
        for(int r=1;r<n;r++){
            if(T[r-1]!=T[r]){
                mod(node(l,r-1,T[r-1]),1);
                l=r;
            }
        }
        mod(node(l,n-1,T[n-1]),1);
    };
    function<bool(node,node)> intersect=[&](node a,node b){
        if(b<a) swap(a,b);
        return (a.r>=b.l);
    };
    function<void(node)> upd=[&](node v){
        auto it=prev(seg.upper_bound(v));
        /*node left=(*it);
        mod(left,-1);
        if(v.l>left.l){
            node nleft=node(left.l,v.l-1,left.c);
            mod(nleft,1);
        }
        if(v.r<left.r){
            node nleft=node(v.r+1,left.r,left.c);
            mod(nleft,1);
        }
        it=seg.upper_bound(v);*/
        while(it!=seg.end() and intersect((*it),v)){
            node cur=(*it);
            mod(cur,-1);
            if(v.l>cur.l){
                node ncur=node(cur.l,v.l-1,cur.c);
                mod(ncur,1);
            }
            if(v.r<cur.r){
                node ncur=node(v.r+1,cur.r,cur.c);
                mod(ncur,1);
            }
            it=seg.lower_bound(v);
        }
        mod(v,1);
    };
    function<void()> check=[&](){
        /*for(auto v:seg){
            cout<<v.l<<' '<<v.r<<' '<<v.c<<'\n';
        }*/
        for(int i=0;i<9;i++){
            if(ok[i]==0){
                cout<<"Yes"<<'\n';
                return;
            }
        }
        cout<<"No"<<'\n';
        return;
    };
    string T;
    cin>>T;
    init(T);
    check();
    for(int i=0;i<q;i++){
        int l,r;
        char c;
        cin>>l>>r>>c;
        l--;
        r--;
        upd(node(l,r,c));
        check();
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//diaoborz
/*
3
IJO
JII
III
10
OOO
3 3 J
1 3 O
2 3 I
3 3 I
1 2 J
1 2 J
1 2 O
2 2 I
3 3 J
1 2 J
No
Yes
No
Yes
Yes
No
No
No
Yes
No
No

*/

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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