oj.uz

Submission #1117977

# Submission time Handle Problem Language Result Execution time Memory
1117977 2024-11-24T14:19:11 Z Icelast Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 914 ms 977812 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 4e6+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 = maxn;
    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

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

# Verdict Execution time Memory Grader output
1 Correct 805 ms 955208 KB Output is correct
2 Correct 741 ms 955208 KB Output is correct
3 Correct 741 ms 955416 KB Output is correct
4 Correct 787 ms 955208 KB Output is correct
5 Correct 856 ms 955292 KB Output is correct
6 Correct 847 ms 955448 KB Output is correct
7 Correct 780 ms 955444 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 889 ms 971064 KB Output is correct
2 Correct 865 ms 974448 KB Output is correct
3 Correct 829 ms 975040 KB Output is correct
4 Correct 845 ms 974264 KB Output is correct
5 Correct 911 ms 977452 KB Output is correct
6 Correct 895 ms 977812 KB Output is correct
7 Correct 871 ms 961240 KB Output is correct
8 Correct 890 ms 973056 KB Output is correct
9 Correct 842 ms 971208 KB Output is correct
10 Correct 849 ms 968248 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 958756 KB Output is correct
2 Correct 814 ms 958032 KB Output is correct
3 Correct 721 ms 958440 KB Output is correct
4 Correct 890 ms 957768 KB Output is correct
5 Correct 771 ms 957588 KB Output is correct
6 Correct 804 ms 958108 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 955208 KB Output is correct
2 Correct 741 ms 955208 KB Output is correct
3 Correct 741 ms 955416 KB Output is correct
4 Correct 787 ms 955208 KB Output is correct
5 Correct 856 ms 955292 KB Output is correct
6 Correct 847 ms 955448 KB Output is correct
7 Correct 780 ms 955444 KB Output is correct
8 Correct 889 ms 971064 KB Output is correct
9 Correct 865 ms 974448 KB Output is correct
10 Correct 829 ms 975040 KB Output is correct
11 Correct 845 ms 974264 KB Output is correct
12 Correct 911 ms 977452 KB Output is correct
13 Correct 895 ms 977812 KB Output is correct
14 Correct 871 ms 961240 KB Output is correct
15 Correct 890 ms 973056 KB Output is correct
16 Correct 842 ms 971208 KB Output is correct
17 Correct 849 ms 968248 KB Output is correct
18 Correct 832 ms 958756 KB Output is correct
19 Correct 814 ms 958032 KB Output is correct
20 Correct 721 ms 958440 KB Output is correct
21 Correct 890 ms 957768 KB Output is correct
22 Correct 771 ms 957588 KB Output is correct
23 Correct 804 ms 958108 KB Output is correct
24 Correct 794 ms 973644 KB Output is correct
25 Correct 834 ms 975372 KB Output is correct
26 Correct 914 ms 972664 KB Output is correct
27 Correct 886 ms 973128 KB Output is correct
28 Correct 910 ms 969016 KB Output is correct
29 Correct 843 ms 965192 KB Output is correct