Submission #1157558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157558		blueviolet	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	518 ms	604124 KiB

selling_rna

#include             <bits/stdc++.h>
    
#define             ll   long long
#define            pll   pair<ll, ll>
#define            pii   pair<int, int>
#define          io(x)   if (fopen(x".inp","r")) {freopen(x".inp","r",stdin),freopen(x".out","w",stdout);}
#define      mem(c, x)   memset(c, x, sizeof(c))
#define         all(c)   c.begin(), c.end()
#define       bit(i,j)   ((i >> j) & 1)
#define             pb   push_back
#define             se   second     
#define             fi   first
#define             el   '\n'
using namespace std;  

template<class T> bool   maximize(T &a, const T &b) { return (a < b ? a = b, 1 : 0); }
template<class T> bool   minimize(T &a, const T &b) { return (a > b ? a = b, 1 : 0); }

int dx[8] = {0, 1, 0,-1, 1, 1,-1,-1};
int dy[8] = {1, 0,-1, 0, 1,-1,-1, 1};
const int  maxn  = 1e5 + 9;
const int  Inf   = 2e9 + 7;
const ll   Infll = 1e18 + 9;
const ll   Mod   = 1e9 + 7;
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
int n, m;
string s[maxn];

bool cmp(string a, string b) {
    for (int i=0; i<min((int)a.size(), (int)b.size()); i++) {
        if (a[i] > b[i]) return 0;
        if (a[i] < b[i]) return 1;
    }
    return (int)a.size() < (int)b.size();
}

struct Trie
{
    struct node {
        node* child[26];
        int l, r;
        node() {
            for (int i=0; i<26; i++) child[i] = NULL;
            l = r = 0;
        }
    };
    node* root;
    Trie() {
        root = new node();
    }
    void add(string s, int pos) {
        node* u = root;
        for (char x : s) {
            int c = x-'A';
            if (u->child[c] == NULL) {
                u->child[c] = new node();
            }
            u = u->child[c];
            if (!u->l) {
                u->l = pos;
            }
            u->r = pos;
        }
    }
    pii query(string s) {
        node* u = root;
        for (char x : s) {
            int c = x-'A';
            if (u->child[c] == NULL) break;
            u = u->child[c];
        }
        return make_pair(u->l, u->r);
    }
}trie;

struct TrieVer2
{
    struct node {
        node* child[26];
        vector<int> vec;
        node() {
            for (int i=0; i<26; i++) child[i] = NULL;
            vec.clear();
        }
    };
    node* root;
    TrieVer2() {
        root = new node();
    }
    void add(string s, int pos) {
        node* u = root;
        for (char x : s) {
            int c = x-'A';
            if (u->child[c] == NULL) {
                u->child[c] = new node();
            }
            u = u->child[c];
            u->vec.pb(pos);
        }
    }
    void query(pii seq, string s) {
        node* u = root;
        for (char x : s) {
            int c = x-'A';
            if (u->child[c] == NULL) {
                cout << 0 << el;
                return;
            }
            u = u->child[c];
        }
        int l = lower_bound(all(u->vec), seq.fi) - u->vec.begin();
        int r = upper_bound(all(u->vec), seq.se) - u->vec.begin() - 1;
        cout << max(0, r-l+1) << el;
    }
}trieVer2;

void solve() {
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        cin >> s[i];
    } 
    sort(s + 1, s + n + 1, cmp);
    for (int i=1; i<=n; i++) {
        trie.add(s[i], i);
        reverse(all(s[i]));
    }
    for (int i=1; i<=n; i++) {
        trieVer2.add(s[i], i);
    }
    while (m--) {
        string p, q; cin >> p >> q;
        reverse(all(q));
        pii seq = trie.query(p);
        if (seq.fi != -1)
            trieVer2.query(seq, q);
        else
            cout << 0 << el;
    }
}

signed main() {
    
    ios_base::sync_with_stdio(false);  cin.tie(0); cout.tie(0); 
    io("task"); 

    solve();
    
    return (0 ^ 0);
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH ^-^
 */

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:6:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define          io(x)   if (fopen(x".inp","r")) {freopen(x".inp","r",stdin),freopen(x".out","w",stdout);}
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:144:5: note: in expansion of macro 'io'
  144 |     io("task");
      |     ^~
selling_rna.cpp:6:85: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define          io(x)   if (fopen(x".inp","r")) {freopen(x".inp","r",stdin),freopen(x".out","w",stdout);}
      |                                                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:144:5: note: in expansion of macro 'io'
  144 |     io("task");
      |     ^~

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