Submission #771092

#	Time	Username	Problem	Language	Result	Execution time	Memory
771092		davitmarg	Crossing (JOI21_crossing)	C++17	100 / 100	506 ms	40744 KiB

Main

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair    
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 500005;


string crossing(string a, string b)
{
    string s = a;
    for (int i = 0; i < a.length(); i++)
    {
        if (a[i] == b[i])
            continue;
        s[i] = '0' + ((a[i] - '0') ^ (b[i] - '0'));
    }
    return s;
}

string norm(string s)
{
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'J')
            s[i] = '1';
        else if(s[i] == 'O')
			s[i] = '2';
		else
			s[i] = '3';
    }
    return s;
}

int n, q;
string s[N];
map<LL, bool> used;

LL prime = 271;
LL e[N], pr[5][N];

void hashInit()
{
    e[0] = 1;
    for(int i = 1; i <= n; i++)
		e[i] = (e[i - 1] * prime) % mod;

    for (int i = 0; i <= n; i++)
    {
        for (int j = 1; j <= 3; j++)
        { 
            pr[j][i] = (j * e[i]) % mod;
            if(i)
               pr[j][i] = (pr[j][i] + pr[j][i - 1]) % mod;
        }   

    }
}

LL getHash(string s)
{
	LL h = 0;
	for(int i = 0; i < s.length(); i++)
        h = (h + (LL)(s[i] - '0') * e[i]) % mod;
	return h;
}

LL t[4 * N];
char d[4 * N];

void build(int v, int l, int r)
{
    d[v] = '0';
    if (l == r)
    {
        t[v] = (LL)(s[0][l] - '0') * e[l];
        t[v] %= mod;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * v, l, mid);
    build(2 * v + 1, mid + 1, r);
    t[v] = (t[2 * v] + t[2 * v + 1]) % mod;
}

void push(int v, int l, int r)
{
    if(d[v] == '0')
		return;
    if (l != r)
    {
        d[v * 2] = d[v];
        d[v * 2 + 1] = d[v];
    }
    t[v] = (pr[d[v] - '0'][r] - pr[d[v] - '0'][l - 1] + mod) % mod;
    d[v] = '0';
}

LL get(int v, int l, int r, int i, int j)
{
    push(v, l, r);
    if(i > j)
        return 0;
    if (l == i && r == j)
		return t[v];
    int mid = (l + r) / 2;
	LL res = (
        get(2 * v, l, mid, i, min(j, mid)) +
        get(2 * v + 1, mid + 1, r, max(i, mid + 1), j)) % mod;
	return res;
}

void upd(int v, int l, int r, int i, int j, char val)
{
    push(v, l, r);
    if (i > j)
		return;
    if (l == i && r == j)
    {
        d[v] = val;
        push(v, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * v, l, mid, i, min(j, mid), val);
    upd(2 * v + 1, mid + 1, r, max(i, mid + 1), j, val);
    t[v] = (t[2 * v] + t[2 * v + 1]) % mod;
}

void solve()
{
    cin >> n;
    cin >> s[1] >> s[2] >> s[3];
    s[1] = norm(s[1]);
    s[2] = norm(s[2]);
    s[3] = norm(s[3]);

    hashInit();

    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            for (int k = 1; k <= 3; k++)
                used[getHash(crossing(crossing(s[i], s[j]), s[k]))] = 1;

    cin >> q;

    cin >> s[0];
    s[0] = norm(s[0]);

    build(1, 0, n - 1);

    if (used[t[1]])
		cout << "Yes\n";
	else
		cout << "No\n";

    for (int i = 1; i <= q; i++)
    {
        int l, r;
        char c;
        cin >> l >> r >> c;
        if(c == 'J')
            c = '1';
		else if(c == 'O')
            c = '2';
        else
            c = '3';

        upd(1, 0, n - 1, l - 1, r - 1, c);

        if (used[t[1]])
            cout << "Yes\n";
		else
			cout << "No\n";
    }
}


int main()
{
    fastIO;
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

/*


*/

Compilation message (stderr)

Main.cpp: In function 'std::string crossing(std::string, std::string)':
Main.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < a.length(); i++)
      |                     ~~^~~~~~~~~~~~
Main.cpp: In function 'std::string norm(std::string)':
Main.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < s.length(); i++)
      |                     ~~^~~~~~~~~~~~
Main.cpp: In function 'long long int getHash(std::string)':
Main.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i = 0; i < s.length(); i++)
      |                 ~~^~~~~~~~~~~~

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