oj.uz

Submission #697669

# Submission time Handle Problem Language Result Execution time Memory
697669 2023-02-10T17:14:00 Z gagik_2007 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 314 ms 145136 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 145136 KB Output is correct
2 Correct 278 ms 137776 KB Output is correct
3 Correct 145 ms 63256 KB Output is correct
4 Correct 139 ms 60792 KB Output is correct
5 Correct 213 ms 142860 KB Output is correct
6 Correct 212 ms 142856 KB Output is correct
7 Correct 80 ms 15848 KB Output is correct
8 Correct 215 ms 91092 KB Output is correct
9 Correct 179 ms 77800 KB Output is correct
10 Correct 160 ms 80328 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3568 KB Output is correct
2 Correct 53 ms 2640 KB Output is correct
3 Correct 74 ms 3056 KB Output is correct
4 Correct 58 ms 2896 KB Output is correct
5 Correct 55 ms 2628 KB Output is correct
6 Correct 72 ms 3036 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 265 ms 145136 KB Output is correct
9 Correct 278 ms 137776 KB Output is correct
10 Correct 145 ms 63256 KB Output is correct
11 Correct 139 ms 60792 KB Output is correct
12 Correct 213 ms 142860 KB Output is correct
13 Correct 212 ms 142856 KB Output is correct
14 Correct 80 ms 15848 KB Output is correct
15 Correct 215 ms 91092 KB Output is correct
16 Correct 179 ms 77800 KB Output is correct
17 Correct 160 ms 80328 KB Output is correct
18 Correct 87 ms 3568 KB Output is correct
19 Correct 53 ms 2640 KB Output is correct
20 Correct 74 ms 3056 KB Output is correct
21 Correct 58 ms 2896 KB Output is correct
22 Correct 55 ms 2628 KB Output is correct
23 Correct 72 ms 3036 KB Output is correct
24 Correct 274 ms 120208 KB Output is correct
25 Correct 314 ms 120352 KB Output is correct
26 Correct 262 ms 120224 KB Output is correct
27 Correct 158 ms 61640 KB Output is correct
28 Correct 309 ms 34000 KB Output is correct
29 Correct 205 ms 12464 KB Output is correct