Submission #1296577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296577		hoa208	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	172 ms	160792 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
//--------------------------------------------------------------------

const ll N = 1e5 + 10;
const ll C = 2e6 + 10;
ll n, m;
ll ans[N];
string T = "AGCU";
struct TRIE {
    ll child[C][4], node;
    ll st[C], en[C], timedfs;
    ll add(string &s) {
        ll u = 0;
        FOR(i, 0, s.size() - 1) {
            ll k = T.find(s[i]);
            if(child[u][k] == 0) {
                child[u][k] = ++node;
            }
            u = child[u][k];
        }
        return u;
    }
    void dfs(ll u) {
        st[u] = ++timedfs;
        FOR(i, 0, 3) {
            if(child[u][i]) {
                dfs(child[u][i]);
            }
        }
        en[u] = timedfs;
    }
    ll get(string &s) {
        ll u = 0;
        FOR(i, 0, s.size() - 1) {
            ll k = T.find(s[i]);
            if(child[u][k] == 0) return -1;
            u = child[u][k];
        }
        return u;
    }
} trie1, trie2;
const ll maxbit = 2e6 + 2;
ll BIT[maxbit];
void update(ll x, ll val, ll n) {
    while(x <= n) {
        BIT[x] += val;
        x += x & -x;
    }
}
ll get(ll x) {
    ll sum = 0;
    while(x > 0) {
        sum += BIT[x];
        x -= x & -x;
    }
    return sum;
}
struct state {
    ll l, r, id;
};
vector<ll> event_update[C];
vector<state> event_query[C];
void add_update(ll l, ll r) {
    event_update[l].push_back(r);
}
void add_query(ll l, ll r, ll u, ll v, ll id) {
    if(l > 1) event_query[l - 1].push_back({u, v, -id});
    event_query[r].push_back({u, v, id});
}
pa ed[N];
void hbmt() {
	cin >> n >> m;
	FOR(i, 1, n) {
        string s;
        cin >> s;
        ll u_l = trie1.add(s);
        reverse(s.begin(), s.end());
        ll u_r = trie2.add(s);
        ed[i] = {u_l, u_r};
	}
	trie1.dfs(0);
	trie2.dfs(0);
	FOR(i, 1, n) {
        add_update(trie1.st[ed[i].fi], trie2.st[ed[i].se]);
	}
	FOR(i, 1, m) {
        string p, q;
        cin >> p >> q;
        ll u = trie1.add(p);
        reverse(q.begin(), q.end());
        ll v = trie2.add(q);
        if(u == -1 || v == -1) {
            ans[i] = 0;
            continue;
        }
        add_query(trie1.st[u], trie1.en[u], trie2.st[v], trie2.en[v], i);
	}
	ll n1 = trie1.timedfs, n2 = trie2.timedfs;
	FOR(i, 1, n1) {
        for(auto e : event_update[i]) {
            update(e, 1, n2);
        }
        for(auto &e : event_query[i]) {
            ll l = e.l, r = e.r, id = e.id;
            int c = 1;
            if(id < 0) {
                c = -1;
                id = -id;
            }
            ans[id] += c * (get(r) - get(l - 1));
        }
	}
	FOR(i, 1, m) {
        cout << ans[i] << '\n';
	}
}

int main() {

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

	#define NAME "hbmt"
	if(fopen(NAME".inp", "r")) {
		freopen(NAME".inp", "r", stdin);
		freopen(NAME".out", "w", stdout);
	}

	//int t;cin>>t;while(t--)
	hbmt();
	return 0;
}

Compilation message (stderr)

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

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