Submission #1161259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161259		ReLice	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	156 ms	67040 KiB

selling_rna

#include <bits/stdc++.h>
#define ll int
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}

const ll inf = 1e9;
const ll mod = 1e9 + 7;
const ll N = 2e6 + 8;

struct trie{
    ll t[N][4];
    ll tin[N], tout[N];
    ll lst = 1, tiktak;

    ll z(char ch){
        ll x;
        if(ch == 'A') x = 0;
        else if(ch == 'G') x = 1;
        else if(ch == 'C') x = 2;
        else x = 3;

        return x;
    }

    void add(ll cur, ll id, string &s){
        if(id == s.size()) return;

        ll x = z(s[id]);

        if(t[cur][x] == 0) t[cur][x] = ++lst;

        add(t[cur][x], id + 1, s);
    }

    ll get(ll cur, ll id, string &s){
        if(id == s.size()) return cur;

        ll x = z(s[id]);

        return get(t[cur][x], id + 1, s);
    }

    void dfs(ll v){
        tin[v] = ++tiktak;

        for(ll i=0;i<4;i++){
            if(t[v][i] == 0) continue;
            dfs(t[v][i]);
        }

        tout[v] = ++tiktak;
    }
}t, rt;

struct seg{
    ll t[N * 4];
    ll n;

    void upd(ll v, ll tl, ll tr, ll pos, ll val){
        if(tl > pos || tr < pos) return;
        if(tl == tr){
            t[v] += val;
            return;
        }

        ll tm = (tl + tr) / 2;
        upd(v * 2, tl, tm, pos, val);
        upd(v * 2 + 1, tm + 1, tr, pos, val);

        t[v] = t[v * 2] + t[v * 2 + 1];
    }

    void upd(ll pos, ll val){
        upd(1, 1, n, pos, val);
    }

    ll get(ll v, ll tl, ll tr, ll l, ll r){
        if(tl > r || tr < l) return 0;
        if(l <= tl && tr <= r) return t[v];

        ll tm = (tl + tr) / 2;

        return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm + 1, tr, l, r);
    }

    ll get(ll l, ll r){
        return get(1, 1, n, l, r);
    }
}st;

void solve() {
    ll i, j;

    ll n, m;
    cin>>n>>m;

    string s[n];

    for(i=0;i<n;i++){
        cin>>s[i];

        t.add(1, 0, s[i]);
        reverse(all(s[i]));

        rt.add(1, 0, s[i]);
        reverse(all(s[i]));
    }

    vector<string> p(m), q(m);
    for(i=0;i<m;i++){
        cin>>p[i]>>q[i];

        t.add(1, 0, p[i]);

        reverse(all(q[i]));
        rt.add(1, 0, q[i]);
    }

    t.dfs(1);
    rt.dfs(1);

    vector<array<ll, 2>> v;
    vector<array<ll, 4>> sq;

    set<ll> sx = {-1}, sy = {-1};

    for(i=0;i<n;i++){
        ll x = t.get(1, 0, s[i]);
        reverse(all(s[i]));

        ll y = rt.get(1, 0, s[i]);
        reverse(all(s[i]));


        v.pb({t.tin[x], rt.tin[y]});
        sx.ins(t.tin[x]);

        sy.ins(rt.tin[y]);
    }

    for(i=0;i<m;i++){
        ll x = t.get(1, 0,  p[i]);
        ll y = rt.get(1, 0, q[i]);

        sq.pb({t.tin[x], t.tout[x], rt.tin[y], rt.tout[y]});
        sx.ins(t.tin[x] - 1);
        sx.ins(t.tin[x]);
        sx.ins(t.tout[x]);

        sy.ins(rt.tin[y] - 1);
        sy.ins(rt.tin[y]);
        sy.ins(rt.tout[y]);
    }

    map<ll,ll> pos, pp;
    ll c = 0, c2 = 0;

    for(auto i : sx) pos[i] = ++c;
    for(auto i : sy) pp[i] = ++c2;

    vector<ll> ans(m + 5);
    vector<vector<ll>> add(c2 + 5);
    vector<vector<array<ll, 4>>> qq(c2 + 5);

    st.n = c;

    for(i=0;i<n;i++){
        v[i][0] = pos[v[i][0]];
        v[i][1] = pp[v[i][1]];

        add[v[i][1]].pb(v[i][0]);
    }

    for(i=0;i<m;i++){
        sq[i][0] = pos[sq[i][0]];
        sq[i][1] = pos[sq[i][1]];
        sq[i][2] = pp[sq[i][2]];
        sq[i][3] = pp[sq[i][3]];

        qq[sq[i][2] - 1].pb({sq[i][0], sq[i][1], -1, i});
        qq[sq[i][3]].pb({sq[i][0], sq[i][1], 1, i});
    }

    for(i=0;i<=c2;i++){
        for(auto j : add[i]){
            st.upd(j, 1);
        }
        for(auto [l, r, c, id] : qq[i]){
            ans[id] += st.get(l, r) * c;
        }
    }

    for(i=0;i<m;i++){
        cout<<ans[i]<<endl;
    }
}

signed main(){
    start();

    ll t = 1;
    //cin>>t;

    while(t--) solve();
}

/*

*/

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