Submission #1134909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134909		tuongll	Crossing (JOI21_crossing)	C++20	100 / 100	1323 ms	24256 KiB

Main

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <ctime>
#include <cassert>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <bitset>
#include <array>
using ll = long long;
#define debug(x) cout << #x << " = " << x << '\n'
#define separator "===============================================\n"
#define all(a) a.begin(), a.end()
#define SZ(a) (int)(a).size()
using namespace std;
const int mxn = 2e5 + 3;
const ll  mod = 1e9 + 7;
const int inf32 = 2e9;
const ll  inf64 = 3e18;
int n, q;
string joi = "JOI";
int cnt[3][mxn], a[mxn], b[mxn];
int seg[mxn * 4], lazy[mxn * 4];
void build(int id, int l, int r){
    lazy[id] = -1;
    if (l == r){
        seg[id] = a[l] == b[l];
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid), build(id * 2 + 1, mid + 1, r);
    seg[id] = seg[id * 2] + seg[id * 2 + 1];
}
void push(int id, int l, int r){
    if (lazy[id] == -1) return;
    int c = lazy[id], mid = (l + r) / 2;
    if (l != r){
        seg[id * 2] = cnt[c][mid] - cnt[c][l - 1];
        seg[id * 2 + 1] = cnt[c][r] - cnt[c][mid];
        lazy[id * 2] = lazy[id * 2 + 1] = c;
    }
    lazy[id] = -1;
}
void update(int id, int l, int r, int u, int v, int c){
    push(id, l, r);
    if (v < l || r < u) return;
    if (u <= l && r <= v){
        seg[id] = cnt[c][r] - cnt[c][l - 1];
        lazy[id] = c;
        push(id, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, v, c);
    update(id * 2 + 1, mid + 1, r, u, v, c);
    seg[id] = seg[id * 2] + seg[id * 2 + 1];
}
void solve(){
    cin >> n;
    vector<vector<int>> g;
    for (int j = 0; j < 3; ++j){
        string s; cin >> s;
        g.push_back({});
        for (char c : s)
            g.back().push_back(c != 'J' ? c != 'O' ? 2 : 1 : 0);
    }
    auto combine = [&](vector<int>& a, vector<int>& b){
        vector<int> c;
        for (int i = 0; i < n; ++i){
            if (a[i] == b[i]) c.push_back(a[i]);
            else c.push_back(3 - a[i] - b[i]);
        }
        return c;
    };
    while(true){
        bool running = false;
        vector<vector<int>> cand;
        for (int i = 0; i < SZ(g); ++i){
            for (int j = i + 1; j < SZ(g); ++j){
                auto nxt = combine(g[i], g[j]);
                bool flag = true;
                for (auto cur : g)
                    if (nxt == cur) flag = false;
                if (flag){
                    running = true;
                    cand.push_back(nxt);
                }
            }
        }
        for (auto nxt : cand)
            g.push_back(nxt);
        sort(all(g));
        g.erase(unique(all(g)), end(g));
        if (!running) break;
    }
    // 3 seconds just to get all strings :v
    cin >> q;
    vector<int> t;
    {
        string s; cin >> s;
        for (char c : s)
            t.push_back(c != 'J' ? c != 'O' ? 2 : 1 : 0);
    }
    vector<tuple<int, int, int>> queries;
    queries.emplace_back(0, 0, 0);
    for (int _ = 0; _ < q; ++_){
        int l, r, type; char c; cin >> l >> r >> c;
        type = c != 'J' ? c != 'O' ? 2 : 1 : 0;
        queries.emplace_back(l, r, type);
    }
    vector<bool> ans(q + 1, false);
    for (int i = 1; i <= n; ++i)
        b[i] = t[i - 1];
    for (auto s : g){
        for (int i = 1; i <= n; ++i)
            a[i] = s[i - 1];
        for (int i = 1; i <= n; ++i){
            for (int j = 0; j < 3; ++j)
                cnt[j][i] = cnt[j][i - 1];
            ++cnt[a[i]][i];
        }
        build(1, 1, n);
        for (int i = 0; i <= q; ++i){
            int l, r, c; tie(l, r, c) = queries[i];
            update(1, 1, n, l, r, c);
            if (seg[1] == n) ans[i] = true;
        }
    }
    for (int i = 0; i <= q; ++i){
        if (ans[i]) cout << "Yes\n";
        else cout << "No\n";
    }
}
int main(){
	auto start = chrono::steady_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    chrono::duration<double> elapsed {chrono::steady_clock::now() - start};
    cerr << "\n>> Runtime: " << elapsed.count() << "s\n";
}

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