Submission #1035099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035099		CommandMaster	Crossing (JOI21_crossing)	C++17	26 / 100	219 ms	19512 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>

inline int ser(char c) {
    return c == 'J' ? 1 : c == 'O' ? 2 : 3;
}

const ll maxN = 2e5+5;
const ll MOD = 1e9+7;
const ll P = 5;
const ll invP1 = 250000002;

ll powP[maxN];

ll get_hash(string s) {
    ll hash = 0;
    for (int i = 0; i < s.size(); i++) {
        hash += powP[i] * ser(s[i]);
        hash %= MOD;
    }
    return hash;
}

inline ll cohash(ll val, int sz) {
    return val * (powP[sz] - 1) * invP1 % MOD;
}

struct SEG {
    vll toset;
    vll hash;

    void make(ll n) {
        toset.resize(n*4);
        hash.resize(n*4);
    }

    void push(ll v, ll tl, ll tm, ll tr) {
        if (toset[v]) {
            toset[v*2] = toset[v];
            hash[v*2] = cohash(toset[v], tm-tl+1);
            toset[v*2+1] = toset[v];
            hash[v*2+1] = cohash(toset[v], tr-tm);
            toset[v] = 0;
        }
    }

    void pull(ll v, ll tl, ll tm, ll tr) {
        hash[v] = (hash[v*2] + powP[tm - tl + 1] * hash[v*2+1]) % MOD;
    }

    void set(ll v, ll tl, ll tr, ll l, ll r, ll val) {
        if (l > r) return;
        if (tl == l && tr == r) {
            toset[v] = val;
            hash[v] = cohash(val, tr-tl+1);
            return;
        }
        ll tm = (tl + tr) / 2;
        push(v, tl, tm, tr);
        set(v*2, tl, tm, l, min(r, tm), val);
        set(v*2+1, tm+1, tr, max(l, tm+1), r, val);
        pull(v, tl, tm, tr);
    }

    void get(ll v, ll tl, ll tr, ll ind) {
        if (tl == tr) {
            cout << ind << ": " << hash[v] << '\n';
            return;
        }
        ll tm = (tl + tr) / 2;
        push(v, tl, tm, tr);
        if (ind <= tm) get(v*2, tl, tm, ind);
        else get(v*2+1, tm+1, tr, ind);
    }
};

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    ll n;
    cin >> n;
    powP[0] = 1;
    for (int i = 1; i <= n; i++) powP[i] = powP[i-1] * P % MOD;
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;
    ll h = get_hash(s1);
    // cout << "hash: " << h << endl;
    ll q;
    cin >> q;
    SEG seg;
    seg.make(n);
    for (ll i =0 ; i < n; i++) {
        char c;
        cin >> c;
        seg.set(1, 0, n-1, i, i, ser(c));
    }
    // for (int i = 0; i < n; i++) seg.get(1, 0, n-1, i);
    if (seg.hash[1] == h) cout << "Yes\n";
    else cout << "No\n";
    while (q--) {
        ll l, r;
        char c;
        cin >> l >> r >> c;
        l--, r--;
        seg.set(1, 0, n-1, l, r, ser(c));
        // for (int i = 0; i < n; i++) seg.get(1, 0, n-1, i);
        if (seg.hash[1] == h) cout << "Yes\n";
        else cout << "No\n";
    }
}

Compilation message (stderr)

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

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