Submission #1297319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297319		cspercival	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	688 ms	493108 KiB

selling_rna

// Template generated by Clank
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define all(x) x.begin(), x.end()
#define BOOST cin.tie(NULL); ios_base::sync_with_stdio(false);
// #define int ll
typedef long long ll;

pair<int,int> pzero = {-1,-1};

struct Node{
    int next[30] = {0};
    int nw = 0;
    int l = 1e9, r = 0;
    vector<int> ids;
};

struct Trie{
    int root = 1;
    int prectr = 1;
    vector<Node> t;
    Trie(){
        t.resize(2);
    }

    void add_string(string &s, int id){
        int idx = root;
        // cout << t[idx].next[0] << " lol\n";
        for(auto c : s){
            if(!t[idx].next[c - 'A']){
                t[idx].next[c - 'A'] = (int)t.size();
                t.emplace_back();
            }
            idx = t[idx].next[c - 'A'];
        }
        t[idx].ids.push_back(id);
        t[idx].nw++;
    }

    int dfs(int idx, vector<pair<int,int>> &labels){
        // static int prectr = 1;
        t[idx].l = prectr;
        for(int i : t[idx].ids){
            labels[i].st = prectr++;
            t[idx].r = labels[i].st;
        }
        for(int i = 0; i < 30; i++){
            if(t[idx].next[i] != 0){
                t[idx].r = max(t[idx].r, dfs(t[idx].next[i], labels));
            }
        }
        return t[idx].r;
    }

    pair<int,int> get_lim(string &s){
        int idx = root;
        // cout << s << "\n";
        for(int i = 0; i < (int)s.size(); i++){
            if(t[idx].next[s[i] - 'A'] == 0) return pzero;
            idx = t[idx].next[s[i] - 'A'];
            // cout << idx << "\n";
        }
        return {t[idx].l - 1, t[idx].r};
    }
};

struct SegTree{
    int n;
    int shift = 1;
    vector<int> t;
    SegTree(int inn) : n(inn){
        while(shift < n) shift <<= 1;
        t.resize(2 * shift);
    }

    void update(int idx, int val){
        for(idx += shift; idx >= 1; idx >>= 1){
            t[idx] += val;
        }
    }

    int query(int l, int r){
        int sum = 0;
        for(l += shift, r += shift; l < r; l >>= 1, r >>= 1){
            if(l&1) sum += t[l++];
            if(r&1) sum += t[--r];
        }
        return sum;
    }
};

void compute_rect(int n, vector<pair<int,int>> &labels, vector<pair<pair<int,int>, pair<int,int>>> &queries, map<pair<int,int>, int> &rect){
    vector<pair<pair<int,int>, int>> points;
    for(int i = 0; i < n; i++){
        points.push_back({labels[i], -1});
    }
    for(auto i : queries){
        if(i.st == pzero || i.nd == pzero) continue;
        points.push_back({{i.st.st, i.nd.st}, 0});
        points.push_back({{i.st.st, i.nd.nd}, 0});
        points.push_back({{i.st.nd, i.nd.st}, 0});
        points.push_back({{i.st.nd, i.nd.nd}, 0});
    }

    SegTree tree(n + 5);
    sort(all(points));
    for(auto p : points){
        if(p.nd == 0){
            rect[p.st] = tree.query(0, p.st.nd + 1);
        } else {
            tree.update(p.st.nd, abs(p.nd));
        }
    }
}

int32_t main(){
    BOOST;
    int n, m; cin >> n >> m;
    string notes;
    Trie pre;
    Trie suf;
    for(int i = 0; i < n; i++){
        cin >> notes;
        pre.add_string(notes,i); 
        reverse(all(notes));
        suf.add_string(notes, i);
    }
    vector<pair<int,int>> labels(n);
    suf.dfs(1, labels);
    for(int i = 0; i < n; i++) swap(labels[i].st, labels[i].nd);
    pre.dfs(1, labels);

    vector<pair<pair<int,int>, pair<int,int>>> queries;
    string sp, ss;
    for(int i = 0; i < m; i++){
        cin >> sp >> ss;
        reverse(all(ss));
        queries.push_back({pre.get_lim(sp), suf.get_lim(ss)});
    }
    
    // for(int i = 0; i < n; i++){
    //     cout << labels[i].st << " - " << labels[i].nd << "\n";
    // }
    // cout << "\n";
    
    // for(auto i : queries){
    //     cout << i.st.st << " " << i.st.nd << " " << i.nd.st << " " << i.nd.nd << "\n";
    // }
    // cout << labels << "\n";

    // cout << queries << "\n";

    map<pair<int,int>, int> rectangles;
    compute_rect(n, labels, queries, rectangles);
    
    // for(auto i : rectangles){
    //     cout << i.st.st << " " << i.st.nd << " - " << i.nd << "\n";
    // }

    int sum = 0;
    for(auto i : queries){
        sum = 0;
        if(i.st == pzero || i.nd == pzero){
            cout << 0 << "\n";
            continue;
        }
        sum += rectangles[{i.st.st, i.nd.st}];
        sum -= rectangles[{i.st.st, i.nd.nd}];
        sum -= rectangles[{i.st.nd, i.nd.st}];
        sum += rectangles[{i.st.nd, i.nd.nd}];
        cout << sum << "\n";
    }
    return 0;
}

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