Submission #765951

#	Time	Username	Problem	Language	Result	Execution time	Memory
765951		pandapythoner	Crossing (JOI21_crossing)	C++14	100 / 100	1712 ms	155892 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

struct SGT {
    struct node {
        array<int, 3> count = {0, 0, 0};
        int bd_count = 0;
        int d = -1;

        node() {}
        node(int a, int b) {
            count[b] = 1;
            d = a;
            if (a == b) {
                bd_count = 0;
            } else {
                bd_count = 1;
            }
        }

        void apply(int a) {
            d = a;
            bd_count = count[0] + count[1] + count[2] - count[a];
        }
    };

    void merge(const node &a, const node &b, node &c) {
        c.d = -1;
        c.count[0] = a.count[0] + b.count[0];
        c.count[1] = a.count[1] + b.count[1];
        c.count[2] = a.count[2] + b.count[2];
        c.bd_count = a.bd_count + b.bd_count;
    }

    int n;
    vector<node> t;

    void push(int v) {
        if (t[v].d != -1) {
            t[v + v].apply(t[v].d);
            t[v + v + 1].apply(t[v].d);
            t[v].d = -1;
        }
    }

    void upd(int v) {
        merge(t[v + v], t[v + v + 1], t[v]);
    }

    void build(int v, int tl, int tr, vector<int> &a, vector<int> &b) {
        if (tl == tr) {
            t[v] = node(a[tl], b[tl]);
            return;
        }
        int tm = (tl + tr) / 2;
        build(v + v, tl, tm, a, b);
        build(v + v + 1, tm + 1, tr, a, b);
        upd(v);
    }

    void build(vector<int> &a, vector<int> &b) {
        n = a.size();
        t.resize(n * 4);
        build(1, 0, n - 1, a, b);
    }

    void chng(int v, int tl, int tr, int l, int r, int x) {
        if (tr < l || r < tl) {
            return;
        }
        if (l <= tl && tr <= r) {
            t[v].apply(x);
            return;
        }
        push(v);
        int tm = (tl + tr) / 2;
        chng(v + v, tl, tm, l, r, x);
        chng(v + v + 1, tm + 1, tr, l, r, x);
        upd(v);
    }

    void chng(int l, int r, int x) {
        chng(1, 0, n - 1, l, r, x);
    }

    bool get() {
        return t[1].bd_count == 0;
    }
};

int n;
vector<vector<int>> x;
vector<vector<int>> gd;
int gd_sz;
vector<SGT> sgt;

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    x.assign(3, vector<int>(n));
    for (int i = 0; i < 3; i += 1) {
        for (int j = 0; j < n; j += 1) {
            char c;
            cin >> c;
            if (c == 'J') {
                x[i][j] = 0;
            } else if (c == 'O') {
                x[i][j] = 1;
            } else if (c == 'I') {
                x[i][j] = 2;
            }
        }
    }
    gd.clear();
    for (int c0 = 0; c0 < 3; c0 += 1) {
        for (int c1 = 0; c1 < 3; c1 += 1) {
            int c2 = (1 + 2 * c0 + 2 * c1) % 3;
            assert((c0 + c1 + c2) % 3 == 1);
            vector<int> t(n);
            for (int i = 0; i < n; i += 1) {
                t[i] = (x[0][i] * c0 + x[1][i] * c1 + x[2][i] * c2) % 3;
            }
            gd.push_back(t);
        }
    }
    gd_sz = gd.size();
    int q;
    cin >> q;
    vector<int> t0(n);
    for (int i = 0; i < n; i += 1) {
        char c;
        cin >> c;
        if (c == 'J') {
            t0[i] = 0;
        } else if (c == 'O') {
            t0[i] = 1;
        } else if (c == 'I') {
            t0[i] = 2;
        }
    }
    sgt.resize(gd_sz);
    for (int i = 0; i < gd_sz; i += 1) {
        sgt[i].build(t0, gd[i]);
    }
    for (int i = 0; i <= q; i += 1) {
        bool ok = false;
        for (int j = 0; j < gd_sz; j += 1) {
            if (sgt[j].get()) {
                ok = true;
                break;
            }
        }
        if (ok) {
            cout << "Yes"
                 << "\n";
        } else {
            cout << "No"
                 << "\n";
        }
        if(i == q){
            break;
        }
        int l, r;
        char c;
        cin >> l >> r >> c;
        --l;
        --r;
        int aboba;
        if (c == 'J') {
            aboba = 0;
        } else if (c == 'O') {
            aboba = 1;
        } else if (c == 'I') {
            aboba = 2;
        }
        for(int j = 0; j < gd_sz; j += 1){
            sgt[j].chng(l, r, aboba);
        }
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:28:15: warning: 'aboba' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |             d = a;
      |             ~~^~~
Main.cpp:178:13: note: 'aboba' was declared here
  178 |         int aboba;
      |             ^~~~~

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