제출 #658226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658226		Danilo21	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1579 ms	171148 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 segtree{

    int n;
    vector<int> tree;

    int update(int s, int l, int r, int pos, int x){
        if (l > pos || r < pos) return tree[s];
        if (l == r) return tree[s] += x;
        int m = (l + r)>>1;
        int a = update(2*s, l, m, pos, x);
        int b = update(2*s+1, m+1, r, pos, x);
        return tree[s] = a+b;
    }

    int query(int s, int l, int r, int ql, int qr) const {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return tree[s];
        int m = (l + r)>>1;
        int a = query(2*s, l, m, ql, qr);
        int b = query(2*s+1, m+1, r, ql, qr);
        return a+b;
    }

public:
    segtree(int n = 0){ Assign(n); }
    void Assign(int s){
        n = highpow(s);
        if (bitcnt(s) > 1) n <<= 1;
        tree.assign(2*n, 0);
    }
    void update(int pos, int x){ update(1, 0, n-1, pos, x); }
    int query(int l, int r) const { return query(1, 0, n-1, l, r); }
    void Print() const { for (int i = n; i < 2*n; i++) cout << tree[i] << sp; cout << en; }
};

struct Trie{

    static map<char, int> mp;
    int n;
    vector<vector<int> > g;
    vector<int> word, in, out;
    Trie(){ Node(); }
    int Node(){
        g.pb(vector<int>(4, -1));
        word.pb(0);
        in.pb(0);
        out.pb(0);
        return n++;
    }
    int Add(int s, string str, int i){
        if (i == str.size()){
            word[s]++;
            return s;
        }
        int x = mp[str[i]];
        if (!~g[s][x]) g[s][x] = Node();
        return Add(g[s][x], str, i+1);
    }
    int Find(int s, string str, int i) const {
        if (i == str.size()) return s;
        int x = mp[str[i]];
        if (!~g[s][x]) return -1;
        return Find(g[s][x], str, i+1);
    }
    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 = 1e6+10, INF = 2e9;
ll n, m, a[mxN], ans[mxN], mp[mxN];
vector<array<int, 2> > q[mxN];
Trie pre, suf;
segtree st;

void dfs(int s){

    for (auto [u, i] : q[s])
        ans[i] = st.query(suf.in[u], suf.out[u]);
    if (pre.word[s]) st.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] = st.query(suf.in[u], suf.out[u]) - ans[i];
}

void Solve(){

    memset(mp, -1, sizeof(mp));
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        rs(s);
        int u = pre.Add(0, s, 0);
        reverse(all(s));
        int v = suf.Add(0, s, 0);
        mp[u] = v;
    }
    pre.Compute();
    suf.Compute();
    st.Assign(suf.n);
    for (int i = 0; i < m; i++){
        rs(s); rs(t);
        reverse(all(t));
        int u = pre.Find(0, s, 0);
        int v = suf.Find(0, t, 0);
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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