Submission #940362

#	Time	Username	Problem	Language	Result	Execution time	Memory
940362		Sundavar	Crossing (JOI21_crossing)	C++14	100 / 100	4498 ms	339616 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int conv(char c){
    if(c == 'I') return 0;
    if(c == 'J') return 1;
    return 2;
}

struct segTree{
    struct node{
        vector<int> real_cnt;
        node(){
            real_cnt.resize(3);
        }
        int wrong = 0, set_to = -1, all = 0;
    };
    vector<node> t;
    int maxN = (1<<18);
    segTree(string& real, string& fake){
        t.resize(2*maxN);
        for(int i = 0; i < real.size(); i++){
            t[i+maxN].real_cnt[conv(real[i])] = 1;
            t[i+maxN].wrong = fake[i] != real[i];
            t[i+maxN].all = 1;
        }
        build(1, 0, maxN);
    }
    void build(int v, int l, int r){
        if(r-l == 1) return;
        build(2*v, l, (l+r)/2), build(2*v+1, (l+r)/2, r);
        t[v].all = t[v*2].all + t[v*2+1].all;
        t[v].wrong = t[v*2].wrong + t[v*2+1].wrong;
        for(int i = 0; i < 3; i++)
            t[v].real_cnt[i] = t[v*2].real_cnt[i]+t[v*2+1].real_cnt[i];

    }
    void add(int v, int c){
        t[v].wrong = t[v].all - t[v].real_cnt[c];
        t[v].set_to = c; 
    }
    void push(int v){
        if(t[v].set_to == -1) return;
        add(2*v, t[v].set_to), add(2*v+1, t[v].set_to);
        t[v].set_to = -1;
    }
    void upd(int l, int r, int c){
        upd(1, l, r, 0, maxN, c);
    }
    void upd(int v, int ll, int rr, int l, int r, int c){
        if(min(r,rr) <= max(l,ll)) return;
        if(ll <= l && r <= rr){
            add(v, c);
            return;
        }
        push(v);
        upd(2*v, ll, rr, l, (l+r)/2, c), upd(2*v+1, ll, rr, (l+r)/2, r, c);
        t[v].wrong = t[v*2].wrong + t[v*2+1].wrong;
    }
};

char cross(char c1, char c2){
    if(c2 < c1) swap(c1, c2);
    if(c1 == c2) return c1;
    if(c1 == 'I' && c2 == 'O') return 'J';
    if(c1 == 'I' && c2 == 'J') return 'O';
    return 'I';
}

int main(){
    int n;
    cin>>n;
    set<string> v;
    for(int i = 0; i < 3; i++){
        string s;
        cin>>s;
        v.insert(s);
    }
    while(true){
        bool added = false;
        for(auto it = v.begin(); it != v.end(); it++)
            for(auto it2 = v.begin(); it2 != it; it2++){
                string s1 = *it, s2 = *it2;
                string s = "";
                for(int k = 0; k < n; k++)
                    s += cross(s1[k], s2[k]);
                if(v.count(s) == 0){
                    added = true;
                    v.insert(s);
                }
            }
        if(!added) break;
    }
    int q;
    string fake;
    cin>>q>>fake;
    vector<segTree> trees;
    for(auto it = v.begin(); it != v.end(); it++){
        string s = *it;
        trees.push_back(segTree(s, fake));
    }
    bool any = false;
    for(int i = 0; i < trees.size(); i++)
        any |= trees[i].t[1].wrong == 0;
    cout << (any ? "Yes" : "No") << "\n";

    while(q--){
        int a, b;
        char c;
        cin>>a>>b>>c;
        bool any = false;
        for(int i = 0; i < trees.size(); i++){
            trees[i].upd(a-1, b, conv(c));
            any |= trees[i].t[1].wrong == 0; 
        }
        cout << (any ? "Yes" : "No") << "\n";
    }
}

Compilation message (stderr)

Main.cpp: In constructor 'segTree::segTree(std::string&, std::string&)':
Main.cpp:21:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int i = 0; i < real.size(); i++){
      |                        ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0; i < trees.size(); i++)
      |                    ~~^~~~~~~~~~~~~~
Main.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int i = 0; i < trees.size(); i++){
      |                        ~~^~~~~~~~~~~~~~

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