oj.uz

답안 #1048158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1048158 2024-08-08T03:13:07 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 167 ms 183888 KB 
#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];
        }
    }

    vector <int> trace(string s) {
        int pos = 0;
        vector <int> res;
        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];
            res.push_back(in[pos]);
        }
        return res;
    }

    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));
        vector <int> tmp1 = t1.trace(s[i]), tmp2 = t2.trace(tmp);
        reverse(all(tmp2));
        for(int j = 0; j < tmp1.size(); ++j) {
            x[tmp1[j]].push_back(tmp2[j]);
        }
    }

    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;
        if(p1.fi > p2.fi) swap(p1.fi, p2.fi);
        if(p1.se > p2.se) swap(p2.se, p1.se);
//        cout << i << ' ' << p1.fi << ' ' << p1.se << ' ' << p2.fi << ' ' << p2.se << '\n';

        query[p1.fi - 1].push_back({p1.se, p2.se, i, 0});
        query[p2.fi].push_back({p1.se, p2.se, i, 1});
        maxx = max({maxx, p1.fi, p2.fi});
        maxy = max({maxy, p1.se, 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

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for(int j = 0; j < tmp1.size(); ++j) {
      |                        ~~^~~~~~~~~~~~~
selling_rna.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 113500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 167 ms 183888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 117792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 113500 KB Output isn't correct
2 Halted 0 ms 0 KB -