Submission #1279911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279911		tin24_mvu	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	185 ms	218540 KiB

selling_rna

#include <bits/stdc++.h>

#define name "rna"
#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 ll long long
#define fi first
#define se second
#define ii pair <int, int>
#define sz(a) a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define MASK(x) (1ll << x)
#define bit(x, i) ((x >> i) & 1)
#define pop_count(x) __builtin_popcount(x)
#define mingdu signed main()

using namespace std;

const ll mod = 998244353;

void add(ll& a, ll b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

void mx(int& a, int b) {if (b > a) a = b;}
void mn(int& a, int b) {if (b < a) a = b;}

ll mul1(ll a, ll b) {
    return ((a % mod) * (b % mod)) % mod;
}

ll mul2(ll a, ll b) {
    ll res = 0;
    while (b) {
        if (b & 1) add(res, a);
        add(a, a);
        b >>= 1;
    }
    return res;
}

ll pw1(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = mul1(res, a);
        a = mul1(a, a);
        b >>= 1;
    }
    return res;
}

ll pw2(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = mul2(res, a);
        a = mul2(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 1e6 + 5;
int n, q;
string s[N];

int change(char x) {
    if (x == 'A') return 0;
    if (x == 'C') return 1;
    if (x == 'G') return 2;
    return 3;
}

struct trie {
    struct node {
        node* child[4];
        int l, r;
        node() {
            FOR(i, 0, 3) child[i] = 0;
            l = 2e9, r = 0;
        }
    };

    node* root;

    trie() {
        root = new node();
    }

    void add(const string& s, const int& cnt) {
        int n = sz(s) - 1;
        node* p = root;
        FOR(i, 0, n) {
            int x = change(s[i]);
            if (!p -> child[x]) p -> child[x] = new node();
            p = p -> child[x];
            mx(p -> r, cnt);
            mn(p -> l, cnt);
        }
    }

    ii get(const string& s) {
        int l, r;
        int n = sz(s) - 1;
        node* p = root;

        FOR(i, 0, n) {
            int x = change(s[i]);
            if (!p -> child[x]) return {2e9, 2e9};
            p = p -> child[x];
        }

        return {p -> l, p -> r};
    }
};

struct rev_trie {
    struct node {
        node* child[4];
        vector <int> id;
        node() {
            FOR(i, 0, 3) child[i] = 0;
            id.clear();
        }
    };

    node* root;

    rev_trie() {
        root = new node();
    }

    void add(string s, const int& cnt) {
        reverse(s.begin(), s.end());
        int n = sz(s) - 1;
        node* p = root;
        FOR(i, 0, n) {
            int x = change(s[i]);
            if (!p -> child[x]) p -> child[x] = new node();
            p = p -> child[x];
            p -> id.pb(cnt);
        }
    }

    int get(const string &s, const ii& k) {
        int l = k.fi, r = k.se;
        if (l == r && l == 2e9) return 0;
        int n = sz(s) - 1;
        node* p = root;

        FOR(i, 0, n) {
int x = change(s[i]);
            if (!p -> child[x]) return 0;
            p = p -> child[x];
        }

        return upper_bound(all(p -> id), r) - lower_bound(all(p -> id), l);
    }
};

void nhap() {
    cin >> n >> q;
    FOR(i, 1, n) cin >> s[i];
}

void giai() {
    trie tree1;
    rev_trie tree2;
    sort(s + 1, s + 1 + n);

    FOR(i, 1, n) {
        tree1.add(s[i], i);
        tree2.add(s[i], i);
    }

    while (q--) {
        string p, q; cin >> p >> q;
        reverse(q.begin(), q.end());
        cout << tree2.get(q, tree1.get(p)) << "\n";
    }
}

mingdu {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    nhap();
    giai();

    return 0;
}

Compilation message (stderr)

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

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