Submission #1117976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117976		Icelast	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	2291 ms	1048576 KiB

selling_rna

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 3e6+5, INF = 4e18+9;
struct Trie{
    struct Node{
        int child[4];
        int cnt = 0, exist = 0;
    } nodes[maxn*4];
    int cur = 0;
    Trie(){
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
    }
    int new_node(){
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        return cur;
    }
    void add(vector<int> a){
        int pos = 0;
        for(int c : a){
            if(nodes[pos].child[c] == -1){
                nodes[pos].child[c] = new_node();
            }
            pos = nodes[pos].child[c];
            nodes[pos].cnt++;
        }
        nodes[pos].exist++;
    }
    int find(vector<int> a){
        int pos = 0;
        for(int c : a){
            if(nodes[pos].child[c] == -1){
                return -1;
            }
            pos = nodes[pos].child[c];
        }
        return pos;
    }
    vector<int> lt, rt;
    int timer;
    void dfs(){
        auto dfs = [&](auto dfs, int u) -> void{
            timer++;
            lt[u] = timer;
            for(int i = 0; i < 4; i++){
                int v = nodes[u].child[i];
                if(v == -1) continue;
                dfs(dfs, v);
            }
            rt[u] = timer;
        };
        lt.resize(cur+1);
        rt.resize(cur+1);
        timer = 0;
        dfs(dfs, 0);
    }

};
struct que{
    int l, r, id, t;
};
struct point{
    int x, y;
};
template <class T>
struct Fenwick {
    int n, log;
    vector<T> bit;

    Fenwick(int n) : n(n), log(32 - __builtin_clz(n + 1)), bit(n + 1, 0) {}

    void add(int i, T delta) {
        for (; i <= n; i += i & -i) {
            bit[i] += delta;
        }
    }

    T sum(int i) {
        T res = 0;
        for (; i > 0; i -= i & -i) {
            res += bit[i];
        }
        return res;
    }
    T sum(int l, int r) {
        T res = 0;
        return sum(r)-sum(l-1);
    }
    int kth(T k) {
        T sum = 0;
        int pos = 0;
        for (int l = log - 1; l >= 0; l--) {
            if (pos + (1 << l) <= n && sum + bit[pos + (1 << l)] <= k) {
                pos += 1 << l;
                sum += bit[pos];
            }
        }
        return pos;
    }
};
void solve(){
    int n, m;
    cin >> n >> m;
    auto conv = [&](char c) -> int{
        if(c == 'A') return 0;
        if(c == 'G') return 1;
        if(c == 'C') return 2;
        if(c == 'U') return 3;
        return -1;
    };
    Trie T1, T2;
    vector<point> a(n+1);
    for(int i = 1; i <= n; i++){
        string S;
        cin >> S;
        vector<int> s;
        for(char c : S){
            s.push_back(conv(c));
        }
        T1.add(s);
        int x = T1.find(s);
        reverse(s.begin(), s.end());
        T2.add(s);
        int y = T2.find(s);
        a[i] = {x, y};
    }
    T1.dfs();
    T2.dfs();
    for(int i = 1; i <= n; i++){
        a[i] = {T1.lt[a[i].x], T2.lt[a[i].y]};
    }
    int N = T1.cur+5;
    vector<vector<que>> sweepQ(N+1);
    vector<vector<point>> sweepA(N+1);
    vector<int> ans(m+1, 0);
    for(int i = 1; i <= n; i++){
        sweepA[a[i].x].push_back(a[i]);
    }
    for(int i = 1; i <= m; i++){
        string P, Q;
        cin >> P >> Q;
        vector<int> ap, aq;
        for(char c : P){
            ap.push_back(conv(c));
        }
        for(char c : Q){
            aq.push_back(conv(c));
        }
        reverse(aq.begin(), aq.end());
        int u1 = T1.find(ap), u2 = T2.find(aq);
        if(u1 == -1 || u2 == -1){
            ans[i] = 0;
        }else{
            sweepQ[T1.lt[u1]-1].push_back({T2.lt[u2], T2.rt[u2], i, -1});
            sweepQ[T1.rt[u1]].push_back({T2.lt[u2], T2.rt[u2], i, 1});
        }
    }
    Fenwick<int> bit(N+1);
    for(int i = 1; i <= N; i++){
        for(auto it : sweepA[i]){
            bit.add(it.y, 1);
        }
        for(auto it : sweepQ[i]){
            ans[it.id] += (ll)it.t*bit.sum(it.l, it.r);
        }
    }
    for(int i = 1; i <= m; i++){
        cout << ans[i] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Compilation message (stderr)

selling_rna.cpp: In instantiation of 'T Fenwick<T>::sum(int, int) [with T = int]':
selling_rna.cpp:166:54:   required from here
selling_rna.cpp:88:11: warning: unused variable 'res' [-Wunused-variable]
   88 |         T res = 0;
      |           ^~~

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