Submission #1186169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186169		user192837	Crossing (JOI21_crossing)	C++17	0 / 100	53 ms	13452 KiB

Main

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
int t[2][N << 2][2], val[N << 2], lazy[N << 2], ql, qr, qi, qx;

void push(int v, int l, int r) {
    if (lazy[v] == -1)
        return;
    val[v] = 1;
    if (l != r)
        lazy[v << 1] = lazy[v << 1 | 1] = lazy[v],
        val[v] &= (val[v << 1] & val[v << 1 | 1]);
    t[1][v][0] = t[1][v][1] = lazy[v];
    val[v] &= (t[0][v][0] == t[1][v][0]) && (t[1][v][1] = t[0][v][1]);
    lazy[v] = -1;
}

void update(int v, int l, int r) {
    if (l == r)
        return t[0][v][0] = t[0][v][1] = qx, void();
    int m = l + r >> 1;
    if (qi <= m)
        update(v << 1, l, m);
    else
        update(v << 1 | 1, m + 1, r);
    t[0][v][0] = min(t[0][v << 1][0], t[0][v << 1 | 1][0]);
    t[0][v][1] = max(t[0][v << 1][1], t[0][v << 1 | 1][1]);
}

void upd(int v, int l, int r) {
    push(v, l, r);
    if (ql <= l && r <= qr) {
        lazy[v] = qx;
        push(v, l, r);
        return;
    }
    if (ql > r || l > qr)
        return;
    int m = l + r >> 1;
    upd(v << 1, l, m);
    upd(v << 1 | 1, m + 1, r);
    t[1][v][0] = min(t[1][v << 1][0], t[1][v << 1 | 1][0]);
    t[1][v][1] = max(t[1][v << 1][1], t[1][v << 1 | 1][1]);
    val[v] = (val[v << 1] & val[v << 1 | 1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n;
    string a, b, c, ts;
    cin >> a >> b >> c;
    for (int i = 0; i < (N << 2); i++)
        t[0][i][0] = t[1][i][0] = 27;
    a = "1" + a;
    for (int i = 1; i <= n; i++)
        qi = i, qx = a[i] - 'A', update(1, 1, n);
    cin >> q >> ts;
    ts = "1" + ts;
    for (int i = 1; i <= n; i++)
        ql = qr = i, qx = ts[i] - 'A', upd(1, 1, n);
    cout << (val[1] ? "Yes\n" : "No\n");
    while (q--) {
        char c;
        cin >> ql >> qr >> c;
        qx = c - 'A';
        upd(1, 1, n);
        cout << (val[1] ? "Yes\n" : "No\n");
    }
}

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