Submission #697669

#	Time	Username	Problem	Language	Result	Execution time	Memory
697669		gagik_2007	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	314 ms	145136 KiB

selling_rna

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

const int K = 4;

struct V1 {
    int l, r;
    int to[K];
    V1() {
        l = r = -1;
        for (int i = 0; i < K; i++) {
            to[i] = -1;
        }
    }
};

struct V2 {
    int to[K];
    vector<int>inds;
    V2() {
        for (int i = 0; i < K; i++) {
            to[i] = -1;
        }
    }
};

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 100007;
ll n, m, k;
vector<V1>t1(1);
vector<V2>t2(1);
int vl[256];
vector<string>h;

void add_v1(const string& s, int i) {
    int v = 0;
    if (t1[v].l == -1) {
        t1[v].l = i;
    }
    t1[v].r = i;
    for (char ch : s) {
        int c = vl[ch];
        if (t1[v].to[c] == -1) {
            t1[v].to[c] = t1.size();
            t1.emplace_back();
        }
        if (t1[t1[v].to[c]].l == -1) {
            t1[t1[v].to[c]].l = i;
        }
        t1[t1[v].to[c]].r = i;
        v = t1[v].to[c];
    }
}

void add_v2(const string& s, int i) {
    //cout << "ADDING V2: " << s << " " << i << endl;
    int v = 0;
    t2[v].inds.push_back(i);
    for (char ch : s) {
        int c = vl[ch];
        if (t2[v].to[c] == -1) {
            t2[v].to[c] = t2.size();
            t2.emplace_back();
        }
        t2[t2[v].to[c]].inds.push_back(i);
        v = t2[v].to[c];
    }
}

void sort_v2(int v) {
    sort(t2[v].inds.begin(), t2[v].inds.end());
    for (int i = 0; i < K; i++) {
        if (t2[v].to[i] != -1) {
            sort_v2(t2[v].to[i]);
        }
    }
}

pair<int, int>get_v1(const string& p) {
    int v = 0;
    for (char ch : p) {
        v = t1[v].to[vl[ch]];
        if (v == -1)return { -1,-1 };
    }
    return { t1[v].l,t1[v].r };
}

int get_v2(const string& q) {
    int v = 0;
    for (char ch : q) {
        v = t2[v].to[vl[ch]];
        if (v == -1)return -1;
    }
    return v;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    vl['A'] = 0;
    vl['C'] = 1;
    vl['G'] = 2;
    vl['U'] = 3;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        h.push_back(s);
    }
    sort(h.begin(), h.end());
    for (int i = 0; i < h.size(); i++) {
        add_v1(h[i], i);
        reverse(h[i].begin(), h[i].end());
        add_v2(h[i], i);
    }
    sort_v2(0);
    //cout << t1.size() << " " << t2.size() << endl;
    for (int i = 0; i < m; i++) {
        string p, q;
        cin >> p >> q;
        reverse(q.begin(), q.end());
        pair<int, int>lr = get_v1(p);
        int l = lr.ff;
        int r = lr.ss;
        int ind = get_v2(q);
        //cout << l << " " << r << " " << ind << endl;
        if (l == -1) {
            cout << 0 << endl;
        }
        else if (ind == -1) {
            cout << 0 << endl;
        }
        else {
            auto it1 = lower_bound(t2[ind].inds.begin(), t2[ind].inds.end(), l);
            auto it2 = upper_bound(t2[ind].inds.begin(), t2[ind].inds.end(), r);
            cout << it2 - it1 << endl;
        }
    }
    return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Compilation message (stderr)

selling_rna.cpp: In function 'void add_v1(const string&, int)':
selling_rna.cpp:69:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   69 |         int c = vl[ch];
      |                    ^~
selling_rna.cpp: In function 'void add_v2(const string&, int)':
selling_rna.cpp:87:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |         int c = vl[ch];
      |                    ^~
selling_rna.cpp: In function 'std::pair<int, int> get_v1(const string&)':
selling_rna.cpp:109:25: warning: array subscript has type 'char' [-Wchar-subscripts]
  109 |         v = t1[v].to[vl[ch]];
      |                         ^~
selling_rna.cpp: In function 'int get_v2(const string&)':
selling_rna.cpp:118:25: warning: array subscript has type 'char' [-Wchar-subscripts]
  118 |         v = t2[v].to[vl[ch]];
      |                         ^~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (int i = 0; i < h.size(); i++) {
      |                     ~~^~~~~~~~~~

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