oj.uz

Submission #862751

# Submission time Handle Problem Language Result Execution time Memory
862751 2023-10-19T01:08:27 Z mgl_diamond Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 95 ms 74544 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"
 
void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 1e5+5;
int id[256];

void prep() {
  id['A'] = 0;
  id['G'] = 1;
  id['C'] = 2;
  id['U'] = 3;
}

struct node {
  int child[4];
  int mn = N, mx = -N, cnt = 0;
  node() { memset(child, -1, sizeof(child)); }
};

int n, m, ret[N];
string s[N], q[N];
vector<node> trie(1);
vector<int> evts[N];

void add(string s, int idx) {
  int cur = 0, n = s.size();
  for(char c : s) {
    int ch = id[c];
    if (trie[cur].child[ch] == -1) {
      trie[cur].child[ch] = sz(trie);
      trie.push_back(node());
    }
    cur = trie[cur].child[ch];
    trie[cur].cnt += 1;
    trie[cur].mn = min(trie[cur].mn, idx);
    trie[cur].mx = max(trie[cur].mx, idx);
  }
}

int get(string s) {
  int cur = 0;
  for(char c : s) {
    int ch = id[c];
    if (trie[cur].child[ch] == -1) return -1;
    cur = trie[cur].child[ch];
  }
  return cur;
}

int main() {
  setIO();

  prep();
  cin >> n >> m;

  foru(i, 1, n) cin >> s[i];
  sort(s+1, s+n+1);
  foru(i, 1, n) add(s[i], i);

  foru(i, 1, m) { 
    string p;
    cin >> p >> q[i];
    reverse(all(q[i]));

    int tmp = get(p);
    if (tmp != -1) {
      int l = trie[tmp].mn, r = trie[tmp].mx;
      evts[l-1].push_back(-i);
      evts[r].push_back(i);
    }
  }

  trie.clear();
  trie.push_back(node());

  foru(i, 1, n) {
    reverse(all(s[i]));
    add(s[i], i);

    fore(j, evts[i]) {
      if (j < 0) {
        int tmp = get(q[-j]);
        if (tmp != -1) ret[-j] -= trie[tmp].cnt;
      }
      else {
        int tmp = get(q[j]);
        if (tmp != -1) ret[j] += trie[tmp].cnt;
      }
    }
  }

  foru(i, 1, m) {
    cout << ret[i] << "\n";
  }
}

Compilation message

selling_rna.cpp: In function 'void add(std::string, int)':
selling_rna.cpp:48:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   48 |     int ch = id[c];
      |                 ^
selling_rna.cpp:46:16: warning: unused variable 'n' [-Wunused-variable]
   46 |   int cur = 0, n = s.size();
      |                ^
selling_rna.cpp: In function 'int get(std::string)':
selling_rna.cpp:63:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |     int ch = id[c];
      |                 ^
selling_rna.cpp: In function 'void setIO()':
selling_rna.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 9076 KB Output is correct
3 Correct 2 ms 9208 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9088 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 74188 KB Output is correct
2 Correct 63 ms 74544 KB Output is correct
3 Correct 65 ms 70836 KB Output is correct
4 Correct 65 ms 71612 KB Output is correct
5 Correct 51 ms 70484 KB Output is correct
6 Correct 52 ms 70584 KB Output is correct
7 Correct 45 ms 18088 KB Output is correct
8 Correct 70 ms 43964 KB Output is correct
9 Correct 67 ms 42960 KB Output is correct
10 Correct 46 ms 43452 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10472 KB Output is correct
2 Correct 16 ms 10292 KB Output is correct
3 Correct 18 ms 10204 KB Output is correct
4 Correct 15 ms 10004 KB Output is correct
5 Correct 16 ms 10076 KB Output is correct
6 Correct 20 ms 10208 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 9076 KB Output is correct
3 Correct 2 ms 9208 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9088 KB Output is correct
8 Correct 65 ms 74188 KB Output is correct
9 Correct 63 ms 74544 KB Output is correct
10 Correct 65 ms 70836 KB Output is correct
11 Correct 65 ms 71612 KB Output is correct
12 Correct 51 ms 70484 KB Output is correct
13 Correct 52 ms 70584 KB Output is correct
14 Correct 45 ms 18088 KB Output is correct
15 Correct 70 ms 43964 KB Output is correct
16 Correct 67 ms 42960 KB Output is correct
17 Correct 46 ms 43452 KB Output is correct
18 Correct 20 ms 10472 KB Output is correct
19 Correct 16 ms 10292 KB Output is correct
20 Correct 18 ms 10204 KB Output is correct
21 Correct 15 ms 10004 KB Output is correct
22 Correct 16 ms 10076 KB Output is correct
23 Correct 20 ms 10208 KB Output is correct
24 Correct 67 ms 73600 KB Output is correct
25 Correct 73 ms 74040 KB Output is correct
26 Correct 63 ms 74464 KB Output is correct
27 Correct 70 ms 70840 KB Output is correct
28 Correct 95 ms 26812 KB Output is correct
29 Correct 57 ms 14176 KB Output is correct