Submission #881499

#	Time	Username	Problem	Language	Result	Execution time	Memory
881499		Arshi	Crossing (JOI21_crossing)	C++17	100 / 100	650 ms	22852 KiB

Main

/**********************GOD**********************/

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <iterator>
#include <map>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> pll;

#define len                 length()
#define MP                  make_pair
#define fs                  first
#define sc                  second
#define pb                  push_back
#define all(x)              x.begin() , x.end()
#define kill(x)             cout << x , exit(0)
#define lid                 (id << 1)
#define rid                 (lid | 1)
#define mid                 ((r + l) >> 1)

const ll mod = 1000696969;
const ll base = 737;
const ll MXN = 2e5 + 4;

ll n;
set<ll> st;
map<char, ll> mp;
string s[4], t;
ll seg[MXN << 2], lz[MXN << 2];
ll pre[MXN][4];

ll pw(ll a, ll b)
{
    ll c = 1;
    while(b > 0) {
        if(b % 2)
            c = c * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return c;
}

ll Hash(string str)
{
    ll ans = 0;
    for(int i = 1; i <= n; i ++) {
        ll x = pw(base, i - 1);
        ll y = x * mp[str[i]] % mod;
        ans = (ans + y) % mod;
    }
    return ans;
}

void Build(int id = 1, int l = 1, int r = n + 1)
{
    if(r - l < 2) {
        seg[id] = mp[t[l]];
        return;
    }
    Build(lid, l, mid);
    Build(rid, mid, r);
    ll x = pw(base, mid - l);
    seg[id] = (seg[lid] + x * seg[rid] % mod) % mod;
}

void Shift(int id, int l, int r)
{
    if(!lz[id])
        return;
    lz[lid] = lz[rid] = lz[id];
    seg[lid] = pre[mid - l][lz[id]];
    seg[rid] = pre[r - mid][lz[id]];
    lz[id] = 0;
}

void Update(int ql, int qr, int v, int id = 1, int l = 1, int r = n + 1)
{
    if(qr <= l || r <= ql)
        return;
    if(ql <= l && r <= qr) {
        seg[id] = pre[r - l][v];
        lz[id] = v;
        return;
    }
    Shift(id, l, r);
    Update(ql, qr, v, lid, l, mid);
    Update(ql, qr, v, rid, mid, r);
    ll x = pw(base, mid - l);
    seg[id] = (seg[lid] + x * seg[rid] % mod) % mod;
}

string Comb(string a, string b)
{
    string c = a;
    for(int i = 1; i <= n; i ++) {
        if(a[i] == b[i])
            continue;
        if(a[i] == 'J') {
            if(b[i] == 'O')
                c[i] = 'I';
            else
                c[i] = 'O';
        }
        if(a[i] == 'O') {
            if(b[i] == 'J')
                c[i] = 'I';
            else
                c[i] = 'J';
        }
        if(a[i] == 'I') {
            if(b[i] == 'J')
                c[i] = 'O';
            else
                c[i] = 'J';
        }
    }
    return c;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n; mp['J'] = 1; mp['O'] = 2; mp['I'] = 3;
    for(int i = 0; i < 3; i ++) {
        cin >> s[i];
        s[i] ='#' + s[i];
    }

    for(int mask = 1; mask < 8; mask ++) {
        vector<string> vc;
        for(int i = 0; i < 3; i ++)
            if(mask >> i & 1) {
                vc.pb(s[i]);
            }
        ll sz = 1;
        for(ll i = 1; i <= vc.size(); i ++)
            sz *= i;
        for(ll j = 0; j < sz; j ++) {
            string tmp = vc[0];
            for(int i = 1; i < vc.size(); i ++)
                tmp = Comb(tmp, vc[i]);
            ll val = Hash(tmp);
            st.insert(val);
            next_permutation(all(vc));
        }
    }

    for(ll i = 1; i <= n; i ++)
        for(ll j = 1; j < 4; j ++)
            pre[i][j] = (pre[i - 1][j] + j * pw(base, i - 1) % mod) % mod; 
    
    int q; cin >> q >> t;
    t = '#' + t;
    Build();
    if(st.count(seg[1]))
        cout << "Yes\n";
    else
        cout << "No\n";
    while(q --) {
        char c; int l, r;
        cin >> l >> r >> c;
        Update(l, r + 1, mp[c]);
        if(st.count(seg[1]))
            cout << "Yes\n";
        else
            cout << "No\n";
    }

    return 0;
}

/*!
ahkh
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:150:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for(ll i = 1; i <= vc.size(); i ++)
      |                       ~~^~~~~~~~~~~~
Main.cpp:154:30: 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 = 1; i < vc.size(); i ++)
      |                            ~~^~~~~~~~~~~

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