Submission #211199

#	Time	Username	Problem	Language	Result	Execution time	Memory
211199		PeppaPig	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	257 ms	33888 KiB

selling_rna

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5+5;

struct SegmentTreeSum {
    int t[N << 1];
    void update(int x, int k) {
        for(t[x += N] += k; x != 1; x >>= 1)
            t[x >> 1] = t[x] + t[x ^ 1];    
    }

    int query(int l, int r) {
        int ret = 0;
        for(l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
            if(l & 1) ret += t[l++];
            if(r & 1) ret += t[--r];
        }
        return ret;
    }
} t;

int n, q;
int pos[N], idx[N], a[N], b[N], ans[N];
vector<int> L[N], R[N];
vector<string> S, pre, suf;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    iota(pos, pos + N, 0);
    
    cin >> n >> q;

    S.resize(n), pre.resize(q), suf.resize(q);
    for(int i = 0; i < n; i++) cin >> S[i];
    for(int i = 0; i < q; i++) cin >> pre[i] >> suf[i];

    sort(S.begin(), S.end());
    for(int i = 0; i < q; i++) {
        int l = lower_bound(S.begin(), S.end(), pre[i]) - S.begin();
        ++pre[i].back();
        int r = lower_bound(S.begin(), S.end(), pre[i]) - S.begin();
        L[l].emplace_back(i), R[r].emplace_back(i);
    }

    vector<string> rev;
    for(int i = 0; i < n; i++) {
        reverse(S[i].begin(), S[i].end());
        rev.emplace_back(S[i]);
    }
    sort(rev.begin(), rev.end());
    sort(pos, pos + n, [&](int &a, int &b) { return S[a] < S[b]; });
    for(int i = 0; i < n; i++) idx[pos[i]] = i;

    for(int i = 0; i < q; i++) {
        reverse(suf[i].begin(), suf[i].end());
        a[i] = lower_bound(rev.begin(), rev.end(), suf[i]) - rev.begin();
        ++suf[i].back();
        b[i] = lower_bound(rev.begin(), rev.end(), suf[i]) - rev.begin() - 1;
    }

    for(int i = n - 1; ~i; i--) {
        t.update(idx[i], 1);
        for(int x : L[i]) ans[x] += t.query(a[x], b[x]);
        for(int x : R[i]) ans[x] -= t.query(a[x], b[x]);
    }
    for(int i = 0; i < q; i++) cout << ans[i] << '\n';

    return 0;
}

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