Submission #1279938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279938		lha9002	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	161 ms	190304 KiB

selling_rna

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i = l ; i <= r ; ++i)
#define FORD(i,l,r) for(int i = l ; i >= r ; --i)
#define open(FILENAME) freopen(FILENAME".inp","r",stdin);
#define close(FILENAME) freopen(FILENAME".out","w",stdout);
#define ll long long
#define ld long double
#define fi first
#define se second
#define BIT(n,i) ((n >> i) & (1ll))
#define MASK(i) ((1ll) << i)
#define ii pair<int,int>
#define li pair<ll ,int>
#define name "test"
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;
const int N  = 1e5;
const int bl = 450;
const int INF = 2e9;
const ll LINF = 1e18;
const int Mod = 1e9 + 7;
int n,q;
string s[N + 3];
int cal(char c){
    if(c == 'A') return 0;
    if(c == 'U') return 1;
    if(c == 'G') return 2;
    if(c == 'C') return 3;
}
struct trie{
    struct node{
        node* child[4];
        int l ,r;
        node(){
            FOR(i , 0 , 3) child[i] = NULL;
            l = N , r = 0;
        }
    };
    struct node1{
        node1* child[4];
        vector<int> id;
        node1(){
            FOR(i , 0 , 3) child[i] = NULL;
            id.clear();
        }
    };
    node* root = new node();
    node1* root1 = new node1();
    void update(string &s ,int pos){
        node* p = root;
        FOR(i , 0 , s.size() - 1){
            int id1 = cal(s[i]);
            if(p -> child[id1] == NULL) p -> child[id1] = new node();
            p = p -> child[id1];
            p -> l = min(p -> l , pos);
            p -> r = max(p -> r , pos);
        }
    }
    void update1(string &s ,int pos){
        node1* p1 = root1;
        reverse(all(s));
        FOR(i , 0 , s.size() - 1){
            int id1 = cal(s[i]);
            if(p1 -> child[id1] == NULL)
                p1 -> child[id1] = new node1();
            p1 = p1 -> child[id1];
            p1 -> id.pb(pos);
        }
    }
    ii get(string &s){
        node* p = root;
        FOR(i , 0 , s.size() - 1){
            int id1 = cal(s[i]);
            if(p -> child[id1] == NULL) return {-1 , -1};
            p = p -> child[id1];
        }
        return {p -> l , p -> r};
    }
    int get1(string &s , ii p1){
        node1* p =  root1;
        int l = p1.fi;
        int r = p1.se;
        if(l == -1) return 0;
        FOR(i , 0 , s.size() - 1){
            int id1 = cal(s[i]);
            if(p -> child[id1] == NULL) return 0;
            p = p -> child[id1];
        }
        return upper_bound(all(p -> id) , r) - lower_bound(all(p -> id) , l);
    }
} t;
void solve(){
    cin >> n >> q;
    FOR(i , 1 , n) cin >> s[i];
    sort(s + 1 , s + n + 1);
    FOR(i , 1 , n){
        t.update(s[i] , i);
        t.update1(s[i] , i);
    }
    while(q--){
        string s2,s3;
        cin >> s2 >> s3;
        reverse(all(s3));
        cout << t.get1(s3 , t.get(s2)) << "\n";

    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int usaco = 0;
    if(fopen(name".inp" , "r")){
        open(name);
        close(name);
    }
     solve();
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int cal(char)':
selling_rna.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:4:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define open(FILENAME) freopen(FILENAME".inp","r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:116:9: note: in expansion of macro 'open'
  116 |         open(name);
      |         ^~~~
selling_rna.cpp:5:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define close(FILENAME) freopen(FILENAME".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:117:9: note: in expansion of macro 'close'
  117 |         close(name);
      |         ^~~~~

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