Submission #539128

#	Time	Username	Problem	Language	Result	Execution time	Memory
539128		kianaRZV	Crossing (JOI21_crossing)	C++14	0 / 100	565 ms	904 KiB

Main

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

const int maxn = 3e5 + 10, mod = 1e9 + 7;
int n, q;
int a[maxn], b[maxn], c[maxn], d[maxn], lazy[maxn << 2], seg[maxn << 2][3][3];

void init(int id, int qv) {
    for (int i = 0; i < 3; i++) {
        int cnt = 0;
        for (int j = 0; j < 3; j++)
            cnt += seg[id][i][j], seg[id][i][j] = 0;
        seg[id][i][qv] = cnt;
    }
}

void shift(int id) {
    if (lazy[id] == -1) return;
    lazy[2 * id + 1] = lazy[2 * id + 2];
    init(2 * id + 1, lazy[id]);
    init(2 * id + 2, lazy[id]);
    lazy[id] = -1;
}

void build(int id, int l, int r) {
    lazy[id] = -1;
    if (r - l < 2) {
        seg[id][a[l]][d[l]]++;
        return;
    }
    int mid = l + r >> 1;
    build(2 * id + 1, l, mid), build(2 * id + 2, mid, r);
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            seg[id][i][j] = seg[2 * id + 1][i][j] + seg[2 * id + 2][i][j];
}

void update(int id, int l, int r, int ql, int qr, int qv) {
    if (l >= qr || ql >= r)
        return;
    if (ql <= l && r <= qr) {
        lazy[id] = qv;
        return init(id, qv);
    }
    int mid = l + r >> 1;
    shift(id);
    update(2 * id + 1, l, mid, ql, qr, qv);
    update(2 * id + 2, mid, r, ql, qr, qv);
    build(2 * id + 1, l, mid), build(2 * id + 2, mid, r);
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            seg[id][i][j] = seg[2 * id + 1][i][j] + seg[2 * id + 2][i][j];
}

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

void check() {
    cout << (seg[0][0][0] + seg[0][1][1] + seg[0][2][2] == n? "YES\n": "NO\n");
}

void read_input() {
    cin >> n;
    char x;
    for (int i = 0; i < n; i++)
        cin >> x, a[i] = get(x);
    for (int i = 0; i < n; i++)
        cin >> x, b[i] = get(x);
    for (int i = 0; i < n; i++)
        cin >> x, c[i] = get(x);
    cin >> q;
    for (int i = 0; i < n; i++)
        cin >> x, d[i] = get(x);
}

void solve() {
    build(0, 0, n);
    check();
    while(q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        update(0, 0, n, --l, r, get(c));
        check();
    }
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    read_input(), solve();
}
/*   /\_/\
    (= ._.)
    / >0  \>1
*/

Compilation message (stderr)

Main.cpp: In function 'void build(long long int, long long int, long long int)':
Main.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = l + r >> 1;
      |               ~~^~~

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