Submission #959393

#	Time	Username	Problem	Language	Result	Execution time	Memory
959393		Alkaser_ID	Crossing (JOI21_crossing)	C++17	26 / 100	190 ms	25004 KiB

Main

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
// second mod 998244353
const ll N = 3e5 + 5;

ll n; string s, t;
struct nd {
    ll o = 0, j = 0, i = 0;
    ll sm = 0;
} seg[3000006];
char lazy[3000006];
inline void upd(ll node, bool b) {
    if (lazy[node] == 'f') return;
    seg[node].sm = 0;
    char c = lazy[node];
    if (c == 'O') seg[node].sm = seg[node].o;
    if (c == 'J') seg[node].sm = seg[node].j;
    if (c == 'I') seg[node].sm = seg[node].i;
    if (b) {
        lazy[node * 2] = c;
        lazy[node * 2 + 1] = c;
    }
    lazy[node] = 'f';
}
inline void build(ll node, ll l, ll r) {
    lazy[node] = 'f';
    if (l == r) {
        if (s[l] == t[l]) seg[node].sm = 1;
        if (s[l] == 'O') ++seg[node].o;
        else if (s[l] == 'I') seg[node].i++;
        else seg[node].j++;
        return;
    }
    ll mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    seg[node].j = seg[node * 2].j + seg[node * 2 + 1].j;
    seg[node].o = seg[node * 2].o + seg[node * 2 + 1].o;
    seg[node].i = seg[node * 2].i + seg[node * 2 + 1].i;
    seg[node].sm = seg[node * 2].sm + seg[node * 2 + 1].sm;
}
inline void update(ll node, ll l, ll r, ll lx, ll rx, char c) {
    upd(node, (l != r));
    if (l >= lx && r <= rx) {
        lazy[node] = c;
        upd(node, (l != r));
        return;
    }
    else if (l > rx || r < lx) return;
    ll mid = (l + r) / 2;
    update(node * 2, l, mid, lx, rx, c);
    update(node * 2 + 1, mid + 1, r, lx, rx, c);
    seg[node].sm = seg[node * 2].sm + seg[node * 2 + 1].sm;
}
inline bool get() { return seg[1].sm == n; }
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string d;
    s = " "; t = " ";
    cin >> n >> d >> d >> d;
    s += d;
    ll q; cin >> q;
    cin >> d;
    t += d;
    build(1, 1, n);
    if (get()) cout << "Yes\n";
    else cout << "No\n";
    for (; q--;) {
        ll l, r; cin >> l >> r;
        char ch; cin >> ch;
        update(1, 1, n, l, r, ch);
        if (get()) cout << "Yes\n";
        else cout << "No\n";
    }
}

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