oj.uz

Submission #1110728

# Submission time Handle Problem Language Result Execution time Memory
1110728 2024-11-10T09:37:56 Z ljtunas Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 296 ms 267568 KB 
// author : anhtun_hi , nqg
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define reset(h, v)    memset(h, v, sizeof h)
#define Forv(i, a)     for(auto& i : a)
#define For(i, a, b)   for(int i = a; i <= b; ++i)
#define Ford(i, a, b)  for(int i = a; i >= b; --i)
#define c_bit(i)     __builtin_popcountll(i)
#define Bit(mask, i)    ((mask >> i) & 1LL)
#define onbit(mask, i)  ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
using namespace std;
namespace std {
    template <typename T, int D>
    struct _vector : public vector <_vector <T, D - 1>> {
        static_assert(D >= 1, "Dimension must be positive!");
        template <typename... Args>
        _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
    };
    template <typename T> struct _vector <T, 1> : public vector <T> {
        _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
    };
    template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;}
    template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;}
}
const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5;
const int MAXN = 1e6 + 5;
const  ll  mod = 1e9 + 7;
const  ll   oo = 1e18;

//#define int long long

int n, q;
string s[MAXN];

struct Node{
    Node *child[4];
    vector<int> s;
    Node(){
        For(i, 0, 3) child[i] = nullptr;
    }
};

Node *r1 = new Node(), *r2 = new Node();

int idx[50];

void add(const string& x, int i, Node *root){
    Node *r = root;
    Forv(c, x){
        r -> s.push_back(i);
        int k = idx[c - 'A'];
        if (r -> child[k] == nullptr) r -> child[k] = new Node();
//        if(root == r2) cerr << c << '\n';
        r = r -> child[k];
    }
     r -> s.push_back(i);
}

ii get_range(const string& x, Node *root){
    Node *r = root;
    Forv(c, x){
        int k = idx[c - 'A'];
        if (r -> child[k] == nullptr) return {-1, -1};
        r = r -> child[k];
    }
    return {r -> s[0], r -> s.back()};
}

int solve(const string& x, int L, int R){
    Node *r = r2;
    Forv(c, x){
        int k = idx[c - 'A'];
        if (r -> child[k] == nullptr) return 0;
        r = r -> child[k];
    }
    return upper_bound(all(r -> s), R) - lower_bound(all(r -> s), L);
}

void Solve() {
    idx['A' - 'A'] = 0;
    idx['G' - 'A'] = 1;
    idx['C' - 'A'] = 2;
    idx['U' - 'A'] = 3;
    cin >> n >> q;
    For(i, 1, n) {
        cin >> s[i];
    }
    sort(s + 1, s + n + 1);
    For(i, 1, n){
        string x = s[i];
        reverse(all(x));
        add(s[i], i, r1);
        add(x, i, r2);
    }
    while  (q--){
        string a, b;
        cin >> a >> b;
        reverse(all(b));
        ii tmp = get_range(a, r1);
        int l = tmp.fi, r = tmp.se;
//        cerr << l << ' ' << r << '\n';
//        cerr << b << '\n';
        if (!~l) cout << 0 << '\n';
        else cout << solve(b, l, r) << '\n';
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(0);
    if(fopen("JOI16_selling_rna.inp", "r")) {
        freopen("JOI16_selling_rna.inp", "r", stdin);
        freopen("JOI16_selling_rna.out", "w", stdout);
    }

    int t = 1;
//    cin >> t;

    for (int test = 1; test <= t; test++) {
        Solve();
    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen("JOI16_selling_rna.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen("JOI16_selling_rna.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 234056 KB Output is correct
2 Correct 272 ms 223304 KB Output is correct
3 Correct 215 ms 231240 KB Output is correct
4 Correct 207 ms 221776 KB Output is correct
5 Correct 296 ms 264180 KB Output is correct
6 Correct 259 ms 267568 KB Output is correct
7 Correct 74 ms 55660 KB Output is correct
8 Correct 238 ms 185872 KB Output is correct
9 Correct 219 ms 162860 KB Output is correct
10 Correct 177 ms 157544 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 34112 KB Output is correct
2 Correct 27 ms 33720 KB Output is correct
3 Correct 31 ms 33864 KB Output is correct
4 Correct 25 ms 33608 KB Output is correct
5 Correct 20 ms 34040 KB Output is correct
6 Correct 23 ms 33864 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31568 KB Output is correct
2 Correct 6 ms 31568 KB Output is correct
3 Correct 7 ms 31568 KB Output is correct
4 Correct 6 ms 31568 KB Output is correct
5 Correct 6 ms 31736 KB Output is correct
6 Correct 6 ms 31636 KB Output is correct
7 Correct 6 ms 31568 KB Output is correct
8 Correct 254 ms 234056 KB Output is correct
9 Correct 272 ms 223304 KB Output is correct
10 Correct 215 ms 231240 KB Output is correct
11 Correct 207 ms 221776 KB Output is correct
12 Correct 296 ms 264180 KB Output is correct
13 Correct 259 ms 267568 KB Output is correct
14 Correct 74 ms 55660 KB Output is correct
15 Correct 238 ms 185872 KB Output is correct
16 Correct 219 ms 162860 KB Output is correct
17 Correct 177 ms 157544 KB Output is correct
18 Correct 30 ms 34112 KB Output is correct
19 Correct 27 ms 33720 KB Output is correct
20 Correct 31 ms 33864 KB Output is correct
21 Correct 25 ms 33608 KB Output is correct
22 Correct 20 ms 34040 KB Output is correct
23 Correct 23 ms 33864 KB Output is correct
24 Correct 216 ms 198872 KB Output is correct
25 Correct 223 ms 198984 KB Output is correct
26 Correct 214 ms 197140 KB Output is correct
27 Correct 198 ms 197016 KB Output is correct
28 Correct 143 ms 76244 KB Output is correct
29 Correct 76 ms 45732 KB Output is correct