제출 #419753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419753		schse	Crossing (JOI21_crossing)	C++17	100 / 100	6367 ms	73364 KiB

Main

#include <bits/stdc++.h>
using namespace std;

string combine(const string &a, const string &b)
{
    string c = a;
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == b[i])
            c[i] = a[i];
        else if (a[i] == 'J')
            c[i] = (b[i] == 'I' ? 'O' : 'I');
        else if (a[i] == 'O')
            c[i] = (b[i] == 'I' ? 'J' : 'I');
        else if (a[i] == 'I')
            c[i] = (b[i] == 'J' ? 'O' : 'J');
    }
    return c;
}

struct treenode
{
    pair<bool, char> target;
    char lazzy = ' ';
    vector<pair<bool, char>> strings; //singelchar, char
    vector<bool> isidentical;
};

pair<bool, char> operator+(const pair<bool, char> &a, const pair<bool, char> &b)
{
    return {a.first && b.first && a.second == b.second, a.second};
}

vector<pair<bool, char>> operator+(const vector<pair<bool, char>> &a, const vector<pair<bool, char>> &b)
{
    vector<pair<bool, char>> c;
    for (int i = 0; i < a.size(); i++)
        c.push_back(a[i] + b[i]);
    return c;
}

vector<bool> operator&&(const vector<bool> &a, const vector<bool> &b)
{
    vector<bool> c;
    for (int i = 0; i < a.size(); i++)
        c.push_back(a[i] && b[i]);
    return c;
}

treenode operator+(treenode a, treenode b)
{
    return {
        a.target + b.target,
        ' ',
        a.strings + b.strings,
        a.isidentical && b.isidentical,
    };
}

struct setgtree
{
    vector<treenode> tree = vector<treenode>(524288 + 5);

    void pushdown(int i)
    {
        if (tree[i].lazzy == ' ')
            return;
        tree[i * 2].lazzy = tree[i * 2 + 1].lazzy = tree[i].lazzy;
        tree[i * 2].target = tree[i * 2 + 1].target = {true, tree[i].lazzy};

        for (int e = 0; e < tree[i * 2].strings.size(); e++)
            tree[i * 2].isidentical[e] = tree[i * 2].strings[e] == tree[i * 2].target;
        for (int e = 0; e < tree[i * 2 + 1].strings.size(); e++)
            tree[i * 2 + 1].isidentical[e] = tree[i * 2 + 1].strings[e] == tree[i * 2 + 1].target;

        tree[i].lazzy = ' ';
    }

    treenode init(int index, int b, int e, const string &T, const vector<string> &S)
    {
        if (e - b == 1)
        {
            tree[index].target = {true, T[b]};
            for (int i = 0; i < S.size(); i++)
            {
                tree[index].strings.push_back({true, S[i][b]});
                tree[index].isidentical.push_back(S[i][b] == T[b]);
            }
            return tree[index];
        }
        init(index * 2, b, (e + b) / 2, T, S);
        init(index * 2 + 1, (b + e) / 2, e, T, S);
        tree[index] = tree[index * 2] + tree[index * 2 + 1];
        return tree[index];
    }

    treenode upd(int index, int b, int e, int l, int r, char c)
    {
        if (l <= b && e <= r)
        {
            tree[index].target = {true, c};
            for (int i = 0; i < tree[index].strings.size(); i++)
                tree[index].isidentical[i] = tree[index].strings[i] == tree[index].target;
            tree[index].lazzy = c;
            return tree[index];
        }
        if (r <= b || e <= l)
            return tree[index];
        pushdown(index);
        upd(index * 2, b, (e + b) / 2, l, r, c);
        upd(index * 2 + 1, (b + e) / 2, e, l, r, c);
        tree[index] = tree[index * 2] + tree[index * 2 + 1];
        return tree[index];
    }
} tree;

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N, Q;
    set<string> str;
    vector<string> vs;
    string s;
    cin >> N >> s;
    if (str.insert(s).second)
        vs.push_back(s);
    cin >> s;
    if (str.insert(s).second)
        vs.push_back(s);
    cin >> s >> Q;
    if (str.insert(s).second)
        vs.push_back(s);
    for (int i = 0; i < vs.size(); i++)
    {
        for (int e = 0; e < i; e++)
        {
            if (e != i && str.insert(combine(vs[i], vs[e])).second)
                vs.push_back(combine(vs[i], vs[e]));
        }
    }

    string T;
    cin >> T;

    tree.init(1, 0, N, T, vs);
    bool b = false;
    for (const bool &s : tree.tree[1].isidentical)
        b |= s;
    if (b)
        cout << "Yes\n";
    else
        cout << "No\n";
    for (int i = 0, b, e; i < Q; i++)
    {
        char c;
        cin >> b >> e >> c;
        tree.upd(1, 0, N, b - 1, e, c);
        bool x = false;
        for (const bool &s : tree.tree[1].isidentical)
            x |= s;
        if (x)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'std::string combine(const string&, const string&)':
Main.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
Main.cpp: In function 'std::vector<std::pair<bool, char> > operator+(const std::vector<std::pair<bool, char> >&, const std::vector<std::pair<bool, char> >&)':
Main.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
Main.cpp: In function 'std::vector<bool> operator&&(const std::vector<bool>&, const std::vector<bool>&)':
Main.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
Main.cpp: In member function 'void setgtree::pushdown(int)':
Main.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int e = 0; e < tree[i * 2].strings.size(); e++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int e = 0; e < tree[i * 2 + 1].strings.size(); e++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In member function 'treenode setgtree::init(int, int, int, const string&, const std::vector<std::__cxx11::basic_string<char> >&)':
Main.cpp:84:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for (int i = 0; i < S.size(); i++)
      |                             ~~^~~~~~~~~~
Main.cpp: In member function 'treenode setgtree::upd(int, int, int, int, int, char)':
Main.cpp:102:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             for (int i = 0; i < tree[index].strings.size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = 0; i < vs.size(); i++)
      |                     ~~^~~~~~~~~~~

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