oj.uz

답안 #1106296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106296 2024-10-29T18:16:16 Z VinhLuu Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 230728 KB 
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second

using namespace std;

typedef pair<int,int> pii;
const int N = 1e5 + 5;
//const int M = 2e6 + 5;
const int oo = 1e9;

int n, m;
string s[N], a[N], b[N];

char change(char c){
  if(c == 'A') return '1';
  if(c == 'C') return '2';
  if(c == 'G') return '3';
  return '4';
}

struct trie{
  trie* child[6];
  vector<int> w;
  trie(){
    for(int i = 0; i <= 5; i ++) child[i] = NULL;
    w.clear();
  }
};

trie* root;

void add(string &x,int id){
  trie* p = root;
  for(auto i : x){
    int val = (i - '0');
    if(p -> child[val] == NULL){
      p -> child[val] = new trie();
    }
    p = p -> child[val];
    p -> w.push_back(id);
  }
}

int query(string &x,int l,int r){
  trie* p = root;
  for(auto i : x){
    int val = (i - '0');
    if(p -> child[val] == NULL) return 0;
    p = p -> child[val];
  }

//  cerr << x << " " << l << " " << r << " t\n";
//  for(auto j : p -> w) cerr << j << " ";
//  cerr << "\n";

  auto v = upper_bound(p -> w.begin(), p -> w.end(), r);
  auto u = lower_bound(p -> w.begin(), p -> w.end(), l);
  if(v == p -> w.begin()) return 0;
  if(u == p -> w.end()) return 0;
  v--;
  int tu = u - p -> w.begin();
  int tv = v - p -> w.begin();
  if(tu <= tv) return tv - tu + 1;
  return 0;
}


mt19937 rd(15253524352);
int ra(int l,int r){
  return l + rd() % (r - l + 1);
}
const ll mod[2] = {ra(1e9, 2e9), (int)1e9 + 7};
const ll base = 137;

map<ll,int> mx, mi;
int le[N], ri[N];

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  root = new trie();

  cin >> n >> m;
  for(int i = 1; i <= n; i ++){
    cin >> s[i];
    for(int j = 0; j < s[i].size(); j ++){
      s[i][j] = change(s[i][j]);
    }
  }
  sort(s + 1, s + n + 1);

//  for(int i = 1; i <= n; i ++) cerr << s[i] << "\n";


  for(int i = 1; i <= n; i ++){
    ll h[2];
    h[0] = h[1] = 0;
    for(int j : s[i]){
      for(int k = 0; k <= 1; k ++){
        h[k] = (1ll * h[k] * base % mod[k] + (ll)(j - '0')) % mod[k];
      }
      ll H = 1ll * h[0] * mod[1] + h[1];
      mx[H] = i;
      if(mi[H] == 0) mi[H] = i;
    }
    string hk = s[i];
    reverse(hk.begin(), hk.end());
//    cerr << i << " j\n";
//    for(auto j : s[i]) cerr
    add(hk, i);
  }

  for(int i = 1; i <= m; i ++){
    cin >> a[i] >> b[i];
    for(int j = 0; j < a[i].size(); j ++) a[i][j] = change(a[i][j]);
    for(int j = 0; j < b[i].size(); j ++) b[i][j] = change(b[i][j]);
    ll h[2];
    h[0] = h[1] = 0;
    for(int j : a[i]){
      for(int k = 0; k <= 1; k ++){
        h[k] = (h[k] * base % mod[k] + (int)(j - '0')) % mod[k];
      }
    }
    ll H = 1ll * h[0] * mod[1] + h[1];
    le[i] = mi[H], ri[i] = mx[H];
    if(!le[i]){
      cout << 0 << "\n";
      continue;
    }
//    cerr << i << " " << le[i] << " " << ri[i] << " o\n";
    reverse(b[i].begin(), b[i].end());
    cout << query(b[i], le[i], ri[i]) << "\n";
  }


}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int j = 0; j < s[i].size(); j ++){
      |                    ~~^~~~~~~~~~~~~
selling_rna.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int j = 0; j < a[i].size(); j ++) a[i][j] = change(a[i][j]);
      |                    ~~^~~~~~~~~~~~~
selling_rna.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int j = 0; j < b[i].size(); j ++) b[i][j] = change(b[i][j]);
      |                    ~~^~~~~~~~~~~~~
selling_rna.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 10320 KB Output is correct
2 Correct 3 ms 10320 KB Output is correct
3 Correct 3 ms 10320 KB Output is correct
4 Correct 3 ms 10320 KB Output is correct
5 Correct 3 ms 10488 KB Output is correct
6 Correct 3 ms 10320 KB Output is correct
7 Correct 3 ms 10320 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 526 ms 230728 KB Output is correct
2 Correct 427 ms 223048 KB Output is correct
3 Execution timed out 1571 ms 198248 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 11468 KB Output is correct
2 Correct 19 ms 11600 KB Output is correct
3 Correct 22 ms 11872 KB Output is correct
4 Correct 16 ms 11600 KB Output is correct
5 Correct 21 ms 12132 KB Output is correct
6 Correct 23 ms 11856 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 10320 KB Output is correct
2 Correct 3 ms 10320 KB Output is correct
3 Correct 3 ms 10320 KB Output is correct
4 Correct 3 ms 10320 KB Output is correct
5 Correct 3 ms 10488 KB Output is correct
6 Correct 3 ms 10320 KB Output is correct
7 Correct 3 ms 10320 KB Output is correct
8 Correct 526 ms 230728 KB Output is correct
9 Correct 427 ms 223048 KB Output is correct
10 Execution timed out 1571 ms 198248 KB Time limit exceeded
11 Halted 0 ms 0 KB -