제출 #422912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422912		Pety	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	346 ms	129136 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define ld long double
 
using namespace std;
 
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
 

struct trie {
  int id, size;
  trie* sons[4];
  trie() {
    id = 0;
    for (int i = 0; i < 4; i++)
      sons[i] = NULL;
  }
} *pref, *suf;

void add (trie* root, string s) {
  trie* nod = root;
  for (auto ch : s) {
    if (nod->sons[ch - 'A'] == NULL)
      nod->sons[ch - 'A'] = new trie;
    nod = nod->sons[ch - 'A'];
  }
}

trie* findInd (trie* root, string s) {
  trie* nod = root;
  for (auto ch : s) {
    if (nod->sons[ch - 'A'] == NULL)
      return NULL;
    nod = nod->sons[ch - 'A'];
  }
  return nod;
}

int nr = 0;

void dfs (trie* root) {
  root->id = nr++;
  root->size = 1;
  for (int i = 0; i < 4; i++)
    if (root->sons[i] != NULL) {
      dfs(root->sons[i]);
      root->size += root->sons[i]->size;
    }
}

string transform (string s) {
  string a;
  for (auto it : s) {
    if (it == 'A')
      a += 'A';
    if (it == 'C')
      a += 'B';
    if (it == 'G')
      a += 'C';
    if (it == 'U')
      a += 'D';
  }
  return a;
}

int n, m, ans[100002], poz1[100002], poz2[100002];
string a[100002];

struct event {
  int type, x, y, id;
  bool operator < (event other) {
    if (x == other.x)
      if (y == other.y)
        return type < other.type;
      else
        return y < other.y;
    return x < other.x;
  }
} e[500002];

int aib[2000002];

void update (int x) {
  for (int i = x; i <= nr; i += (i & -i))
    aib[i]++;
}

int query (int x) {
  int s = 0;
  for (int i = x; i; i -= (i & -i))
    s += aib[i];
  return s;
}

int main()
{
  pref = new trie;
  suf = new trie;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] = transform(a[i]);
    add(pref, a[i]);
    reverse(a[i].begin(), a[i].end());
    add(suf, a[i]);
  }
  nr = 0;
  dfs(pref);
  nr = 0;
  dfs(suf);
   for (int i = 1; i <= n; i++) {
    poz2[i] = findInd(suf, a[i])->id;
    reverse(a[i].begin(), a[i].end());
    poz1[i] = findInd(pref, a[i])->id; 
    e[i] = {0, poz1[i], poz2[i], 0};
  }
  int ev = n;
  for (int i = 1; i <= m; i++) {
    string b, c;

    cin >> b >> c;
    b = transform(b);
    c = transform(c);
    trie* p1 = findInd(pref, b);
    reverse(c.begin(), c.end());
    trie* p2 = findInd(suf, c);
    if (p1 == NULL || p2 == NULL)
      continue;
    int x1 = p1->id;
    int y1 = p2->id;
    int x2 = p1->id + p1->size - 1;
    int y2 = p2->id + p2->size - 1;
    e[++ev] = {1, x2, y2, i};
    e[++ev] = {1, x1 - 1, y2, -i};
    e[++ev] = {1, x2, y1 - 1, -i};
    e[++ev] = {1, x1 - 1, y1 - 1, i};
  }
  sort(e + 1, e + ev + 1);
  for (int i = 1; i <= ev; i++) {
    if (e[i].type == 0)
      update(e[i].y);
    else {
      if (e[i].id > 0) 
        ans[e[i].id] += query(e[i].y);
      else
        ans[-e[i].id] -= query(e[i].y);
    }
  }
  for (int i = 1; i <= m; i++)
    cout << ans[i] << "\n";
  return 0;
}

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

selling_rna.cpp: In member function 'bool event::operator<(event)':
selling_rna.cpp:73:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   73 |     if (x == other.x)
      |        ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40