Submission #658569

#	Time	Username	Problem	Language	Result	Execution time	Memory
658569		Danilo21	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	455 ms	335536 KiB

selling_rna

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

class BIT{

    int n;
    vector<ll> tree;

    ll query(int pos) const {
        if (pos > n) pos = n;
        ll sum = 0;
        for (; pos; pos -= (pos & (-pos)))
            sum += tree[pos];
        return sum;
    }
public:
    BIT(int s = 0){ Assign(s); }

    void Assign(int s = 0){ n = s; tree.assign(s+1, 0); }

    ll query(int l, int r) const {
        l++; r++;
        if (l > r) return 0;
        return query(r) - query(l-1);
    }

    void update(int pos, ll x){
        pos++;
        if (pos <= 0) return;
        for (; pos <= n; pos += (pos & (-pos)))
            tree[pos] += x;
    }
};

struct Trie{

    static map<char, int> mp;
    int n;
    vector<vector<int> > g;
    vector<int> word, in, out;
    Trie(int mx){
        g.assign(mx, vector<int>(4, -1));
        word.assign(mx, 0);
        in.assign(mx, 0);
        out.assign(mx, 0);
        n = 1;
    }
    int Add(string str){
        int s = 0;
        for (int i = 0; i < str.size(); i++){
            int x = mp[str[i]];
            if (!~g[s][x]) g[s][x] = n++;
            s = g[s][x];
        }
        word[s]++;
        return s;
    }
    int Find(string str) const {
        int s = 0;
        for (int i = 0; i < str.size(); i++){
            int x = mp[str[i]];
            if (!~g[s][x]) return -1;
            s = g[s][x];
        }
        return s;
    }
    int Compute(int s = 0, int t = 0){
        in[s] = t;
        for (int u : g[s])
            if (~u)
                t = Compute(u, t+1);
        return out[s] = t;
    }

    void Print() const {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < 4; j++)
                if (~g[i][j])
                    cout << i << sp << g[i][j] << sp << j << en;
        cout << en;
        for (int i = 0; i < n; i++)
            cout << word[i] << sp << in[i] << sp << out[i] << en;
        cout << en;
    }
};

map<char, int> Trie::mp = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};
const ll LINF = 4e18;
const int mxN = 2e6+10, INF = 2e9;
ll n, m, ans[mxN], mp[mxN];
vector<array<int, 2> > q[mxN];
Trie pre(mxN), suf(mxN);
BIT fen;

void dfs(int s){

    for (auto [u, i] : q[s])
        ans[i] = fen.query(suf.in[u], suf.out[u]);
    if (pre.word[s]) fen.update(suf.in[mp[s]], pre.word[s]);
    for (int u : pre.g[s])
        if (~u)
            dfs(u);
    for (auto [u, i] : q[s])
        ans[i] = fen.query(suf.in[u], suf.out[u]) - ans[i];
}

void Solve(){

    cin >> n >> m;
    for (int i = 0; i < n; i++){
        rs(s);
        int u = pre.Add(s);
        reverse(all(s));
        int v = suf.Add(s);
        mp[u] = v;
    }
    suf.Compute();
    fen.Assign(suf.n);
    for (int i = 0; i < m; i++){
        rs(s); rs(t);
        reverse(all(t));
        int u = pre.Find(s);
        int v = suf.Find(t);
        if (~u && ~v) q[u].pb({v, i});
    }
    dfs(0);
    for (int i = 0; i < m; i++)
        cout << ans[i] << en;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'int Trie::Add(std::string)':
selling_rna.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for (int i = 0; i < str.size(); i++){
      |                         ~~^~~~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::Find(std::string) const':
selling_rna.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for (int i = 0; i < str.size(); i++){
      |                         ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'void dfs(int)':
selling_rna.cpp:125:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |     for (auto [u, i] : q[s])
      |               ^
selling_rna.cpp:131:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  131 |     for (auto [u, i] : q[s])
      |               ^

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