Submission #1049594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049594		voi	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	111 ms	180304 KiB

selling_rna

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
#define lb(s, a) lower_bound(all(s), (a)) - s.begin()
#define ii pair <int, int>
#define fi first
#define se second

using namespace std;

typedef long long ll;

const int ar = 2e6+5;
const ll mod = 1e9+7;
const int oo = 1e9;

int n, m, maxx = 0, maxy = 0;

int cs(char a) {
    if(a == 'C') return 0;
    if(a == 'U') return 1;
    if(a == 'G') return 2;
    return 3;
}

struct Trie {
    struct Node{
        int child[5];
    } nodes[ar];

    int cur;
    Trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof(nodes[cur].child));
    };

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        return cur;
    }

    void add(string s) {
        int pos = 0;
        for (auto f : s) {
            int c = cs(f);
            if (nodes[pos].child[c] == -1) {
                nodes[pos].child[c] = new_node();
            }
            pos = nodes[pos].child[c];
        }
    }

    int trace(string s) {
        int pos = 0;
        for (auto f : s) {
            int c = cs(f);
            pos = nodes[pos].child[c];
        }
        return in[pos];
    }

    int in[ar], out[ar], timeDfs = 0;

    void dfs(int u) {
        in[u] = ++timeDfs;
        for(int i = 0; i < 4; ++i) if(nodes[u].child[i] != -1)
            dfs(nodes[u].child[i]);
        out[u] = timeDfs;
    }

    ii get(string s) {
        int pos = 0;
        for (auto f : s) {
            int c = cs(f);
            if (nodes[pos].child[c] == -1)
                return {-1, -1};
            pos = nodes[pos].child[c];
        }
        return {in[pos], out[pos]};
    }
} t1, t2;

int bit[ar], res[ar], L[ar];
vector <int> x[ar];
struct Query {
    int l, r, i;
    bool t;
};
vector <Query> query[ar];
string s[100005];

void update(int i, int val) {
    for(; i <= maxy; i += i & -i)
        bit[i] += val;
}

int get(int i) {
    if(i == 0) return 0;
    int res = 0;
    for(; i > 0; i -= i & -i)
        res += bit[i];
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "b"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i];
        t1.add(s[i]);
        string tmp = s[i];
        reverse(all(tmp));
        t2.add(tmp);
    }

    t1.dfs(0);
    t2.dfs(0);

    for(int i = 1; i <= n; ++i) {
        string tmp = s[i];
        reverse(all(tmp));
        int tmp1 = t1.trace(s[i]), tmp2 = t2.trace(tmp);
        x[tmp1].push_back(tmp2);
//        cout << i << ' ' << tmp1 << ' ' << tmp2 << '\n';
    }

    string p, q;
    for(int i = 1; i <= m; ++i) {
        cin >> p >> q;
        ii p1 = t1.get(p);
        if(p1.fi == -1) continue;
        reverse(all(q));
        ii p2 = t2.get(q);
        if(p2.fi == -1) continue;
//        cout << i << ' ' << p1.fi << ' ' << p1.se << ' ' << p2.fi << ' ' << p2.se << '\n';
//        if(p1.fi > p2.fi) swap(p1.fi, p2.fi);
//        if(p1.se > p2.se) swap(p2.se, p1.se);

        query[p1.fi - 1].push_back({p2.fi, p2.se, i, 0});
        query[p1.se].push_back({p2.fi, p2.se, i, 1});
        maxx = max({maxx, p1.se});
        maxy = max({maxy, p2.se});
    }

    for(int i = 1; i <= maxx; ++i) {
        for(auto y : x[i])
            update(y, 1);
        for(auto [l, r, j, t] : query[i]) {
            int tmp = get(r) - get(l - 1);
            if(t == 0) L[j] = tmp;
            else res[j] = tmp - L[j];
        }
    }
    for(int i = 1; i <= m; ++i)
        cout << res[i] << '\n';
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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