Submission #839445

#	Time	Username	Problem	Language	Result	Execution time	Memory
839445		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	404 ms	30536 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

namespace BIT{
    int t = 0;
    const int OFFSET = 10;
    vector<vector<pair<int, int>>> a;
    void init(int n){
        a.resize(n + OFFSET*2, vector<pair<int, int>> (1, pair<int, int> (-1, 0)));
    }
    void update(int pos, int val){
        for (pos += OFFSET; pos < a.size(); pos += pos & (-pos))
            a[pos].emplace_back(t, a[pos].back().second + val);
        t++;
    }
    int query(int pos, int t){
        int v = 0;
        for (pos += OFFSET; pos; pos -= pos & (-pos)){
            vector<pair<int, int>> &x = a[pos];
            int p = lower_bound(x.begin(), x.end(), pair<int, int> (t, INT_MAX)) - x.begin() - 1;
            v += x[p].second;
        }
        return v;
    }
}

vector<pair<string, int>> a, b;

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    {
        for (int i=0; i<n; i++){
            string ss; cin >> ss;
            a.emplace_back(ss, i);
            reverse(ss.begin(), ss.end());
            b.emplace_back(ss, i);
        }
        stable_sort(a.begin(), a.end());
        stable_sort(b.begin(), b.end());
        vector<int> p(n), s(n);
        for (int i=0; i<n; i++){
            p[a[i].second] = i;
            s[b[i].second] = i;
        }
        BIT::init(n);
        for (pair<string, int> &x: a){
            BIT::update(s[x.second], 1);
        }
    }
    while (m--){
        string p; cin >> p;
        int startp = lower_bound(a.begin(), a.end(), pair<string, int> (p, 0)) - a.begin();
        int endp = lower_bound(a.begin(), a.end(), pair<string, int> (p + '[', 0)) - a.begin() - 1;

        string q; cin >> q;
        reverse(q.begin(), q.end());
        int startq = lower_bound(b.begin(), b.end(), pair<string, int> (q, 0)) - b.begin();
        int endq = lower_bound(b.begin(), b.end(), pair<string, int> (q + '[', 0)) - b.begin() - 1;

        if (startp > endp || startq > endq){
            cout << "0\n";
        }
        else{
            int s = BIT::query(endq, endp) - BIT::query(startq-1, endp);
            int t = BIT::query(endq, startp-1) - BIT::query(startq-1, startp-1);
            cout << s - t << "\n";
        }
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'void BIT::update(int, int)':
selling_rna.cpp:13:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         for (pos += OFFSET; pos < a.size(); pos += pos & (-pos))
      |                             ~~~~^~~~~~~~~~

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