Submission #1156673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156673		ahmedhali107	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	698 ms	432068 KiB

selling_rna

#include <bits/stdc++.h>

#define all(x) begin(x), end(x)

using namespace std;
using ll = long long;

const char nl = '\n';

template<class T>
struct offline_fenwick2d {
    int n;
    vector<vector<T>> vals, bit;

    T f(T a, T b) {
        return (a + b);
    }

    // upd stores updates in form of [x, y]
    offline_fenwick2d(int n, vector<pair<T, T>> &upd) : n(n), vals(n + 1), bit(n + 1) {
        sort(begin(upd), end(upd), [&](const pair<T, T> &p1, const pair<T, T> &p2) {
            return p1.second < p2.second;
        });
        for (int i = 1; i <= n; i++) {
            vals[i].push_back(0), bit[i].push_back(0);
        }
        for (const auto &[x, y]: upd) {
            for (int i = x; i <= n; i += i & -i) {
                if (y != vals[i].back()) {
                    vals[i].push_back(y), bit[i].push_back(0);
                }
            }
        }
    }

    // largest idx i such that vals[x][i] <= y
    int idx(int x, int y) {
        return upper_bound(begin(vals[x]), end(vals[x]), y) - begin(vals[x]) - 1;
    }

    void update(int x, int y, T v) {
        for (; x <= n; x += x & -x) {
            // vals[x][idx(x, y)] must be exactly y as we built the array based on the updates beforehand
            for (int z = idx(x, y); z < bit[x].size(); z += z & -z) {
                bit[x][z] = f(bit[x][z], v);
            }
        }
    }

    // returns rectangular query from (1, 1) to (x, y)
    T query(int x, int y) {
        T ans = 0;
        for (; x >= 1; x -= x & -x) {
            for (int z = idx(x, y); z >= 1; z -= z & -z) {
                ans = f(ans, bit[x][z]);
            }
        }
        return ans;
    }

    int query(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2) + query(x1 - 1, y1 - 1);
    }
};

struct trie {
    vector<array<int, 26>> tr;
    vector<int> tin, tout;

    trie() {
        tr.assign(1, {});
    }

    int insert(string &s, char shft = 'A') {
        int u = 0;
        for (auto &c: s) {
            if (!tr[u][c - shft]) {
                tr[u][c - shft] = tr.size();
                tr.emplace_back();
            }
            u = tr[u][c - shft];
        }
        return u;
    }

    void build() {
        tin.assign(tr.size(), 0);
        tout.assign(tr.size(), 0);
        int ctime = 0;
        auto dfs = [&](auto &&dfs, int u) -> void {
            tin[u] = ++ctime;
            for (int i = 0; i < 26; i++) {
                int v = tr[u][i];
                if (!v) continue;
                dfs(dfs, v);
            }
            tout[u] = ctime;
        };
        dfs(dfs, 0);
    }

    pair<int, int> range(int u) {
        return {tin[u], tout[u]};
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<pair<int, int>> upds(n);
    trie pre, suf;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int u = pre.insert(s);
        upds[i].first = u;
        reverse(all(s));
        u = suf.insert(s);
        upds[i].second = u;
    }
    vector<pair<int, int>> qpre(q), qsuf(q);
    for (int i = 0; i < q; i++) {
        string p, s;
        cin >> p >> s;
        int u = pre.insert(p);
        qpre[i].first = u;
        reverse(all(s));
        u = suf.insert(s);
        qsuf[i].first = u;
    }
    pre.build();
    suf.build();
    for (auto &[u, v]: upds) {
        u = pre.range(u).first;
        v = suf.range(v).first;
    }
    for (int i = 0; i < q; i++) {
        qpre[i] = pre.range(qpre[i].first);
        qsuf[i] = suf.range(qsuf[i].first);
    }
    int mx = max(pre.tout[0], suf.tout[0]) + 5;
    offline_fenwick2d<int> tree(mx, upds);
    for (auto &[x, y]: upds) tree.update(x, y, 1);
    for (int i = 0; i < q; i++) {
        auto [x1, x2] = qpre[i];
        auto [y1, y2] = qsuf[i];
        cout << tree.query(x1, y1, x2, y2) << nl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40