Submission #1265413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265413		Bahamin	Crossing (JOI21_crossing)	C++20	100 / 100	400 ms	26684 KiB

Main

#include "bits/stdc++.h"

using namespace std;

#define all(a) (a).begin(), (a).end()
#define ll long long
#define sui cin.tie(NULL), cout.tie(NULL), ios_base::sync_with_stdio(false)
#define lid id << 1
#define rid id << 1 | 1
#define mid ((r + l) >> 1)
const int MAX_N = 2e5 + 5;
const int INF = 1e9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int LOG = 30;
const int base = 701;

inline int md(ll x, int MOD) {x %= MOD; return x + (x < 0 ? MOD : 0);}
inline int ADD(ll x, ll y, int MOD) {return md(x+y, MOD);}
inline int SUB(ll x, ll y, int MOD) {return md(x-y, MOD);}
inline int MUL(ll x, ll y, int MOD) {return md(1ll*x*y, MOD);}
inline int POW(ll x, ll y, int MOD) {int res=1; while(y){if(y&1)res=MUL(res, x, MOD); x=MUL(x, x, MOD); y>>=1;} return res;}
inline int DIV(ll x, ll y, int MOD) {return MUL(x, POW(y, MOD-2, MOD), MOD);}

pair<int, int> seg[MAX_N << 2];
int ops[MAX_N << 2];
pair<int, int> po[MAX_N];
pair<int, int> inv = {DIV(1, base - 1, MOD1), DIV(1, base - 1, MOD2)};
vector<int> s1;

void build(int l, int r, int id)
{
    if (l == r - 1)
    {
        seg[id] = {s1[l], s1[l]};
        return;
    }
    build(l, mid, lid);
    build(mid, r, rid);
    seg[id].first = ADD(seg[lid].first, MUL(po[mid - l].first, seg[rid].first, MOD1), MOD1);
    seg[id].second = ADD(seg[lid].second, MUL(po[mid - l].second, seg[rid].second, MOD2), MOD2);
}

void move(int l, int r, int id)
{
    if (l == r - 1 || !ops[id]) return;
    seg[lid].first = MUL(MUL(SUB(po[mid - l].first, 1, MOD1), inv.first, MOD1), ops[id], MOD1);
    seg[lid].second = MUL(MUL(SUB(po[mid - l].second, 1, MOD2), inv.second, MOD2), ops[id], MOD2);
    seg[rid].first = MUL(MUL(SUB(po[r - mid].first, 1, MOD1), inv.first, MOD1), ops[id], MOD1);
    seg[rid].second = MUL(MUL(SUB(po[r - mid].second, 1, MOD2), inv.second, MOD2), ops[id], MOD2);
    ops[lid] = ops[rid] = ops[id];
    ops[id] = 0;
}

void upd(int s, int t, int x, int l, int r, int id)
{
    move(l, r, id);
    if (s <= l && t >= r) 
    {
        ops[id] = x;
        seg[id].first = MUL(MUL(SUB(po[r - l].first, 1, MOD1), inv.first, MOD1), ops[id], MOD1);
        seg[id].second = MUL(MUL(SUB(po[r - l].second, 1, MOD2), inv.second, MOD2), ops[id], MOD2);
        return;
    }
    if (s < mid) upd(s, t, x, l, mid, lid);
    if (t > mid) upd(s, t, x, mid, r, rid);
    seg[id].first = ADD(seg[lid].first, MUL(po[mid - l].first, seg[rid].first, MOD1), MOD1);
    seg[id].second = ADD(seg[lid].second, MUL(po[mid - l].second, seg[rid].second, MOD2), MOD2);
}

pair<int, int> gethash(vector<int> s)
{
    pair<int, int> re;
    for (int i = 0; i < s.size(); i++) re.first = ADD(re.first, MUL(s[i], po[i].first, MOD1), MOD1), re.second = ADD(re.second, MUL(s[i], po[i].second, MOD2), MOD2);
    return re;
}

vector<int> merge(vector<int> a, vector<int> b)
{
    vector<int> c(a.size());
    for (int i = 0; i < a.size(); i++) c[i] = (2 * (a[i] + b[i] - 2)) % 3 + 1;
    return c; 
}

int what(char c)
{
    if (c == 'J') return 1;
    if (c == 'O') return 2;
    return 3;
}

void solve()
{   
    po[0].first = po[0].second = 1;
    for (int i = 1; i < MAX_N; i++) po[i].first = MUL(po[i - 1].first, base, MOD1), po[i].second = MUL(po[i - 1].second, base, MOD2);
    int n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;
    vector<int> a1, b1, c1;
    for (int i = 0; i < n; i++) a1.push_back(what(a[i])), b1.push_back(what(b[i])), c1.push_back(what(c[i]));
    vector<pair<int, int>> al({gethash(a1), gethash(b1), gethash(c1), gethash(merge(a1, b1)), gethash(merge(a1, c1)), gethash(merge(b1, c1)), gethash(merge(a1, merge(b1, c1))), gethash(merge(b1, merge(a1, c1))), gethash(merge(c1, merge(b1, a1)))});
    int q;
    cin >> q;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) s1.push_back(what(s[i]));
    build(0, n, 1);
    bool ok = false;
    for (auto x : al) if (x == seg[1]) ok = true;
    cout << (ok ? "Yes" : "No") << "\n";
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        char c;
        cin >> c;
        upd(l - 1, r, what(c), 0, n, 1);
        bool ok = false;
        for (auto x : al) if (x == seg[1]) ok = true;
        cout << (ok ? "Yes" : "No") << "\n";
    }
}

int main()
{
    sui;
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
}

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