oj.uz

Submission #38142

# Submission time Handle Problem Language Result Execution time Memory
38142 2018-01-02T04:36:03 Z funcsr Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 869 ms 146904 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
#define rep(i,n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;

string convert(string s) {
  string o = "";
  for (char c : s) {
    if (c == 'A') o += 'a';
    else if (c == 'G') o += 'b';
    else if (c == 'C') o += 'c';
    else o += 'd';
  }
  return o;
}
string read() {
  string s;
  cin >> s;
  return convert(s);
}

vector<int> radixSort(int p, vector<int> all, string *src) {
  vector<int> s[4] = {};
  vector<int> ret;
  for (int x : all) {
    if (src[x].size() == p) ret.pb(x);
    else s[src[x][p]-'a'].pb(x);
  }
  rep(k, 4) if (!s[k].empty()) {
    vector<int> r = radixSort(p+1, s[k], src);
    ret.insert(ret.end(), all(r));
  }
  return ret;
}

struct Trie {
  int val;
  Trie *ch[4];
  Trie() : val(0) {
    rep(k, 4) ch[k] = NULL;
  }
  int find(const char *s) {
    if (*s == '\0') return val;
    int k = *s-'a';
    if (ch[k] == NULL) return 0;
    return ch[k]->find(s+1);
  }
  void add(const char *s) {
    if (*s == '\0') {
      val++;
      return;
    }
    val++;
    int k = *s-'a';
    if (ch[k] == NULL) ch[k] = new Trie();
    ch[k]->add(s+1);
  }
  void destroy() {
    rep(k, 4) if (ch[k]) {
      ch[k]->destroy();
      delete ch[k];
    }
  }
};
struct Bucket {
  vector<string> str;
  Trie *trie;
  Bucket() {
    trie = new Trie();
  }
  void add(string s) {
    str.pb(s);
    trie->add(s.c_str());
  }
  void destroy() {
    str.clear();
    trie->destroy();
    delete trie;
  }
};

int N, Q;
string S[100000];
string Qpre[100000], Qsuf[100000];
Bucket data[200000];
int ans[100000];

bool is_prefix_of(const string &S, const string &T) {
  if (T.size() > S.size()) return false;
  rep(i, T.size()) if (T[i] != S[i]) return false;
  return true;
}

int main() {
  cin >> N >> Q;
  rep(i, N) S[i] = read();
  rep(i, Q) Qpre[i] = read(), Qsuf[i] = read();
  vector<int> Si; rep(i, N) Si.pb(i); Si = radixSort(0, Si, S);
  vector<int> Qi; rep(i, Q) Qi.pb(i); Qi = radixSort(0, Qi, Qpre);
  reverse(all(Qi));

  set<P> vs;
  rep(i, N) {
    string srev(S[Si[i]]);
    reverse(all(srev));
    data[i].add(srev);
    vs.insert(P(i, i));
  }
  int V = N;

  for (int q : Qi) {
    string &T = Qpre[q];
    int lo = -1, hi = N;
    while (hi-lo > 1) {
      int mid = (lo+hi)/2;
      if (S[Si[mid]] >= T) hi = mid;
      else lo = mid;
    }
    int l = hi;
    if (l == N || !is_prefix_of(S[Si[l]], T)) continue;
    auto it = vs.lower_bound(P(l, -1));
    while (it != vs.end() && is_prefix_of(S[Si[it->_1]], T)) {
      int t = it->_2;
      if (data[V].str.size() < data[t].str.size()) swap(data[V], data[t]);
      for (string s : data[t].str) data[V].add(s);
      data[t].destroy();
      it = vs.erase(it);
    }
    vs.insert(P(l, V));
    reverse(all(Qsuf[q]));
    ans[q] = data[V].trie->find(Qsuf[q].c_str());
    V++;
  }
  rep(i, Q) cout << ans[i] << "\n";
  return 0;
}

Compilation message

selling_rna.cpp: In function 'std::vector<int> radixSort(int, std::vector<int>, std::__cxx11::string*)':
selling_rna.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (src[x].size() == p) ret.pb(x);
                       ^
selling_rna.cpp: In function 'bool is_prefix_of(const string&, const string&)':
selling_rna.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for (int i=0; i<(n); i++)
                                 ^
selling_rna.cpp:100:3: note: in expansion of macro 'rep'
   rep(i, T.size()) if (T[i] != S[i]) return false;
   ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27416 KB Output is correct
2 Correct 19 ms 27416 KB Output is correct
3 Correct 13 ms 27416 KB Output is correct
4 Correct 6 ms 27416 KB Output is correct
5 Correct 19 ms 27416 KB Output is correct
6 Correct 9 ms 27416 KB Output is correct
7 Correct 6 ms 27416 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 131636 KB Output is correct
2 Correct 569 ms 130428 KB Output is correct
3 Correct 869 ms 130124 KB Output is correct
4 Correct 809 ms 130088 KB Output is correct
5 Correct 773 ms 94900 KB Output is correct
6 Correct 766 ms 95740 KB Output is correct
7 Correct 553 ms 107588 KB Output is correct
8 Correct 673 ms 131148 KB Output is correct
9 Correct 696 ms 131016 KB Output is correct
10 Correct 546 ms 128992 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 38804 KB Output is correct
2 Correct 86 ms 36860 KB Output is correct
3 Correct 109 ms 38468 KB Output is correct
4 Correct 86 ms 36076 KB Output is correct
5 Correct 86 ms 35808 KB Output is correct
6 Correct 109 ms 37348 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27416 KB Output is correct
2 Correct 19 ms 27416 KB Output is correct
3 Correct 13 ms 27416 KB Output is correct
4 Correct 6 ms 27416 KB Output is correct
5 Correct 19 ms 27416 KB Output is correct
6 Correct 9 ms 27416 KB Output is correct
7 Correct 6 ms 27416 KB Output is correct
8 Correct 566 ms 131636 KB Output is correct
9 Correct 569 ms 130428 KB Output is correct
10 Correct 869 ms 130124 KB Output is correct
11 Correct 809 ms 130088 KB Output is correct
12 Correct 773 ms 94900 KB Output is correct
13 Correct 766 ms 95740 KB Output is correct
14 Correct 553 ms 107588 KB Output is correct
15 Correct 673 ms 131148 KB Output is correct
16 Correct 696 ms 131016 KB Output is correct
17 Correct 546 ms 128992 KB Output is correct
18 Correct 173 ms 38804 KB Output is correct
19 Correct 86 ms 36860 KB Output is correct
20 Correct 109 ms 38468 KB Output is correct
21 Correct 86 ms 36076 KB Output is correct
22 Correct 86 ms 35808 KB Output is correct
23 Correct 109 ms 37348 KB Output is correct
24 Correct 553 ms 131456 KB Output is correct
25 Correct 533 ms 132140 KB Output is correct
26 Correct 566 ms 131256 KB Output is correct
27 Correct 816 ms 130972 KB Output is correct
28 Correct 789 ms 146904 KB Output is correct
29 Correct 546 ms 85144 KB Output is correct