제출 #862751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862751		mgl_diamond	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	95 ms	74544 KiB

selling_rna

#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";
  }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40