Submission #643922

#	Time	Username	Problem	Language	Result	Execution time	Memory
643922		boris_mihov	Crossing (JOI21_crossing)	C++17	49 / 100	7030 ms	190788 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;

int n, q;
int code[256];
std::string s[3], t;
std::vector <std::string> all;
std::set <std::string> allS;
struct Node
{
    std::vector <bool> equalTo;
    std::vector <bool> allLetters[3];
    int lazy;

    Node()
    {
        lazy = -1;
        equalTo.resize(all.size());
        allLetters[0].resize(all.size());
        allLetters[1].resize(all.size());
        allLetters[2].resize(all.size());
        std::fill(equalTo.begin(), equalTo.end(), false);
        std::fill(allLetters[0].begin(), allLetters[0].end(), false);
        std::fill(allLetters[1].begin(), allLetters[1].end(), false);
        std::fill(allLetters[2].begin(), allLetters[2].end(), false);
    }
    
} tree[4*MAXN];

std::string xorOfStrings(const std::string &a, const std::string &b)
{
    if (a.empty()) return b;
   
    int letterXor = 'J' ^ 'O' ^ 'I';
    std::string res; res.reserve(n);
    for (int i = 0 ; i <= n-1 ; ++i)
    {
        if (a[i] == b[i]) res += a[i];
        else res += letterXor ^ a[i] ^ b[i];
    }

    return res;
}

Node combine(Node left, Node right)
{
    Node res;
    for (int i = 0 ; i < all.size() ; ++i)
    {
        res.equalTo[i] = left.equalTo[i] && right.equalTo[i];
        for (int j = 0 ; j < 3 ; ++j)
        {
            res.allLetters[j][i] = left.allLetters[j][i] && right.allLetters[j][i];
        }
    }

    return res;
}

void build(int l, int r, int node)
{
    tree[node] = Node();
    if (l == r)
    {
        for (int i = 0 ; i < all.size() ; ++i)
        {
            tree[node].allLetters[code[all[i][l]]][i] = true;
            if (all[i][l] == t[l]) tree[node].equalTo[i] = true;
        }

        return;
    }

    int mid = (l + r) / 2;
    build(l, mid, 2*node);
    build(mid + 1, r, 2*node + 1);
    tree[node] = combine(tree[2*node], tree[2*node + 1]);
}

void push(int node, int l, int r)
{
    if (tree[node].lazy == -1) return;

    std::fill(tree[node].equalTo.begin(), tree[node].equalTo.end(), false);
    for (int i = 0 ; i < all.size() ; ++i)
    {
        if (tree[node].allLetters[tree[node].lazy][i])
        {
            tree[node].equalTo[i] = true;
        }
    }

    if (l < r)
    {
        tree[2*node].lazy = tree[node].lazy;
        tree[2*node + 1].lazy = tree[node].lazy;
    }

    tree[node].lazy = -1;
}

void update(int l, int r, int node, int queryL, int queryR, int queryVal)
{
    push(node, l, r);
    if (queryR <  l || r  < queryL) return;
    if (queryL <= l && r <= queryR)
    {
        tree[node].lazy = queryVal;
        push(node, l, r);
        return;
    }

    int mid = (l + r) / 2;
    update(l, mid, 2*node, queryL, queryR, queryVal);
    update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
    tree[node] = combine(tree[2*node], tree[2*node + 1]);
}

void solve()
{
    code['J'] = 0;
    code['O'] = 1;
    code['I'] = 2;
    all.push_back(s[0]);
    all.push_back(s[1]);
    all.push_back(s[2]);
    allS.insert(s[0]);
    allS.insert(s[1]);
    allS.insert(s[2]);

    for (std::string s1 : allS)
    {
        for (std::string s2 : allS)
        {
            std::string curr = xorOfStrings(s1, s2);
            if (!allS.count(curr))
            {
                allS.insert(curr);
                all.push_back(curr);
            }
        }
    }

    int l, r;
    char qType;
    build(0, n-1, 1);
    bool can = false;
    for (int i = 0 ; i < all.size() ; ++i)
    {
        can |= tree[1].equalTo[i];
    }

    if (can) std::cout << "Yes\n";
    else std::cout << "No\n";
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> l >> r >> qType; --l; --r;
        update(0, n-1, 1, l, r, code[qType]);
        bool can = false;
        for (int i = 0 ; i < all.size() ; ++i)
        {
            can |= tree[1].equalTo[i];
        }

        if (can) std::cout << "Yes\n";
        else std::cout << "No\n";
    }
}

void read()
{
    std::cin >> n;
    std::cin >> s[0];
    std::cin >> s[1];
    std::cin >> s[2];
    std::cin >> q;
    std::cin >> t;
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'Node combine(Node, Node)':
Main.cpp:54:24: 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]
   54 |     for (int i = 0 ; i < all.size() ; ++i)
      |                      ~~^~~~~~~~~~~~
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:71:28: 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]
   71 |         for (int i = 0 ; i < all.size() ; ++i)
      |                          ~~^~~~~~~~~~~~
Main.cpp:73:49: warning: array subscript has type 'char' [-Wchar-subscripts]
   73 |             tree[node].allLetters[code[all[i][l]]][i] = true;
      |                                                 ^
Main.cpp: In function 'void push(int, int, int)':
Main.cpp:91:24: 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]
   91 |     for (int i = 0 ; i < all.size() ; ++i)
      |                      ~~^~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:154:24: 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]
  154 |     for (int i = 0 ; i < all.size() ; ++i)
      |                      ~~^~~~~~~~~~~~
Main.cpp:164:38: warning: array subscript has type 'char' [-Wchar-subscripts]
  164 |         update(0, n-1, 1, l, r, code[qType]);
      |                                      ^~~~~
Main.cpp:166:28: 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]
  166 |         for (int i = 0 ; i < all.size() ; ++i)
      |                          ~~^~~~~~~~~~~~

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