제출 #788175

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788175		anton	Crossing (JOI21_crossing)	C++17	100 / 100	3294 ms	39168 KiB

Main

#include<bits/stdc++.h>

using namespace std;


const int MAX_N = 2*1e5;

struct Node{
    bool ok;
    int v;
    Node(bool _ok, int _v){
        ok = _ok;
        v= _v;
    }
    Node(){
        ok = true;
    }
};
Node op(Node& a, Node& b){
    if(a.ok && b.ok){
        if(a.v == b.v){
            return Node(true, a.v);
        }
        return Node(false, -1);
    }
    return Node(false, -1);
}

struct Tree{
    int s, m;
    map<int, int> small;
    vector<Node> tree;
    vector<Node> model;
    vector<bool> ac;
    vector<Node> d;

    Tree(){s= 0;};

    Tree (vector<Node>& mo, vector<Node>& v, map<int, int> sm){
        s = v.size();
        m = 1;

        while(m<s){
            m*=2;
        }
        m*=2;
        tree.resize(m);
        d.resize(m);
        model.resize(m);
        ac.resize(m, false);

        swap(small, sm);
        build(v,mo,  0, s-1, 1);
    }

    void ap(int id){
        tree[id] =d[id];
        if(tree[id].ok && model[id].ok){
            tree[id].v = (tree[id].v- model[id].v+3)%3;
        }
        else{
            tree[id].ok = false;
        }
    }

    void push(int t, int lt, int rt){
        if(lt!=rt && ac[t]){
            d[t*2] = d[t];
            ac[t] = false;
            ac[t*2] =true;
            ac[t*2+1]=true;
            d[t*2+1] = d[t];
            ap(t*2);
            ap(t*2+1);
            tree[t] = op(tree[t*2], tree[t*2+1]);
        }
    }


    void build(vector<Node>&v, vector<Node>& mo, int lt, int rt, int t){
        if(lt == rt){
            model[t] = mo[lt];
            d[t] = v[lt];
            ap(t);
        }
        else{
            int mid = (lt+rt)/2;

            build(v,mo, lt, mid, t*2);
            build(v,mo, mid+1, rt, t*2+1);
            model[t]= op(model[t*2], model[t*2+1]);
            tree[t] = op(tree[t*2], tree[t*2+1]);
        }
    }

    

    void update(int l, int r, Node v, int lt, int rt, int t){
        if(l<=lt && rt<=r){
            d[t] = v;
            ac[t] = true;
            ap(t);
        }
        else if(r<lt|| rt<l){
            return;
        }
        else{
            int mid = (lt+rt)/2;

            push(t, lt, rt);

            /*push(t*2, lt, mid);
            push(t*2+1, mid+1, rt);*/

            update(l, r, v, lt, mid, t*2);
            update(l, r, v, mid+1, rt, t*2+1);
            tree[t] = op(tree[t*2], tree[t*2+1]);
        }

        //cout<<lt<<" "<<rt<<" "<<tree[t].v<<endl;
    }
    void request(int l, int r, int v){

        auto l_it = small.lower_bound(l);
        auto r_it = small.upper_bound(r);

        if(r_it==small.begin()){
            return;
        }
        r_it--;

        if(l_it!=small.end() && r_it!=small.end() && l_it->second <= r_it -> second){
            //cout<<(l_it->first)<<" "<<(r_it->first)<<endl;
            update(l_it->second, r_it->second, Node(true, v), 0, s-1, 1);
        }
    }
}forest[3][3];

int n, q, v[3][3], t[MAX_N][2];
bool is_set[3][3];
string s[3], r;

bool upd_val(int x, int y, int val){
    if(!is_set[x][y]){
        is_set[x][y] = true;
        v[x][y] = val;
    }
    else{
        if(v[x][y] != val){
            return false;
        }
    }
    return true;
}

signed main(){
    cin>>n;

    for(int i = 0; i<3; i++){
        cin>>s[i];
    }

    map<char, int> m;
    m['J'] = 0;
    m['O'] = 1;
    m['I'] = 2;

    for(int i = 0; i<n; i++){
        t[i][0] =(m[s[1][i]] -m[s[0][i]] +3)%3;
        t[i][1] =(m[s[2][i]] - m[s[0][i]] + 3)%3;

    }

    fill(&is_set[0][0], &is_set[0][0] + sizeof(is_set), false);

    cin>>q;
    cin>>r;

    for(int x=0; x<3; x++){
        for(int y = 0; y<3; y++){
            vector<Node> v, mod;

            map<int, int> small;
            for(int i = 0; i<n; i++){
                if(t[i][0] == x && t[i][1] == y){
                    v.push_back(Node(true, m[r[i]]));
                    mod.push_back(Node(true, m[s[0][i]]));
                    small.insert(pair<int, int>(i, small.size()));
                }
            }

            if(v.size()>0){
                forest[x][y] = Tree(mod, v, small);
            }
        }
    }

    bool ok = true;

    is_set[0][0] = true;
    v[0][0] =0;

    for(int i = -1; i<q; i++){
        
        ok = true;
        fill(&is_set[0][0], &is_set[0][0] + sizeof(is_set), false);

        is_set[0][0] = true;

        if(i >=0){
            int l, ri;
            char c;
            cin>>l>>ri>>c;
            l--;
            ri--;

            for(int x=0; x<3; x++){
                for(int y = 0; y<3; y++){
                    if(forest[x][y].s>0){
                        forest[x][y].request(l, ri, m[c]);
                    }
                }
            }
        }

        for(int x=0; x<3; x++){
            for(int y = 0; y<3; y++){
                if(forest[x][y].s>0){
                    is_set[x][y] = forest[x][y].tree[1].ok;
                    ok &= forest[x][y].tree[1].ok;
                    v[x][y] = forest[x][y].tree[1].v;

                    if(x==0 && y==0){
                        ok &= v[x][y]==0;
                    }
                }
            }
        }


        for(int i = 0; i<9; i++){
            for(int b= 0; b<9; b++){
                for(int e = 0; e<9; e++){
                    if(is_set[b/3][b%3] && is_set[e/3][e%3]){
                        ok &= upd_val((e/3 + b/3)%3, (e+b)%3, (v[e/3][e%3] + v[b/3][b%3])%3);
                    }
                }
            }
        }

        if(ok){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }   
    }
}

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