oj.uz

Submission #658569

# Submission time Handle Problem Language Result Execution time Memory
658569 2022-11-13T13:28:06 Z Danilo21 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 455 ms 335536 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 313468 KB Output is correct
2 Correct 249 ms 313416 KB Output is correct
3 Correct 259 ms 313460 KB Output is correct
4 Correct 278 ms 313428 KB Output is correct
5 Correct 266 ms 313452 KB Output is correct
6 Correct 257 ms 313448 KB Output is correct
7 Correct 264 ms 313396 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 332664 KB Output is correct
2 Correct 422 ms 332332 KB Output is correct
3 Correct 381 ms 325556 KB Output is correct
4 Correct 410 ms 327424 KB Output is correct
5 Correct 415 ms 335324 KB Output is correct
6 Correct 404 ms 335536 KB Output is correct
7 Correct 371 ms 319252 KB Output is correct
8 Correct 360 ms 330728 KB Output is correct
9 Correct 349 ms 328880 KB Output is correct
10 Correct 361 ms 326060 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 314700 KB Output is correct
2 Correct 306 ms 314312 KB Output is correct
3 Correct 372 ms 314504 KB Output is correct
4 Correct 303 ms 314164 KB Output is correct
5 Correct 303 ms 314192 KB Output is correct
6 Correct 310 ms 314372 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 313468 KB Output is correct
2 Correct 249 ms 313416 KB Output is correct
3 Correct 259 ms 313460 KB Output is correct
4 Correct 278 ms 313428 KB Output is correct
5 Correct 266 ms 313452 KB Output is correct
6 Correct 257 ms 313448 KB Output is correct
7 Correct 264 ms 313396 KB Output is correct
8 Correct 425 ms 332664 KB Output is correct
9 Correct 422 ms 332332 KB Output is correct
10 Correct 381 ms 325556 KB Output is correct
11 Correct 410 ms 327424 KB Output is correct
12 Correct 415 ms 335324 KB Output is correct
13 Correct 404 ms 335536 KB Output is correct
14 Correct 371 ms 319252 KB Output is correct
15 Correct 360 ms 330728 KB Output is correct
16 Correct 349 ms 328880 KB Output is correct
17 Correct 361 ms 326060 KB Output is correct
18 Correct 325 ms 314700 KB Output is correct
19 Correct 306 ms 314312 KB Output is correct
20 Correct 372 ms 314504 KB Output is correct
21 Correct 303 ms 314164 KB Output is correct
22 Correct 303 ms 314192 KB Output is correct
23 Correct 310 ms 314372 KB Output is correct
24 Correct 426 ms 330700 KB Output is correct
25 Correct 455 ms 331572 KB Output is correct
26 Correct 375 ms 330368 KB Output is correct
27 Correct 435 ms 329320 KB Output is correct
28 Correct 415 ms 322052 KB Output is correct
29 Correct 388 ms 319036 KB Output is correct