oj.uz

Submission #422883

# Submission time Handle Problem Language Result Execution time Memory
422883 2021-06-10T13:36:31 Z Pety Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 360 ms 109872 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
 
using namespace std;
 
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
 
ifstream fin ("rollercoaster.in");
ofstream fout ("rollercoaster.out");

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)
      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);
  trie* aux = new trie;
   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;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:111:9: warning: unused variable 'aux' [-Wunused-variable]
  111 |   trie* aux = new trie;
      |         ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 360 ms 109872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 8516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3404 KB Output isn't correct
2 Halted 0 ms 0 KB -