oj.uz

Submission #422912

# Submission time Handle Problem Language Result Execution time Memory
422912 2021-06-10T14:00:59 Z Pety Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 346 ms 129136 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;
 

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

Compilation message

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.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 106092 KB Output is correct
2 Correct 284 ms 105596 KB Output is correct
3 Correct 293 ms 102096 KB Output is correct
4 Correct 291 ms 97612 KB Output is correct
5 Correct 307 ms 127032 KB Output is correct
6 Correct 316 ms 129136 KB Output is correct
7 Correct 219 ms 11540 KB Output is correct
8 Correct 342 ms 82028 KB Output is correct
9 Correct 317 ms 70644 KB Output is correct
10 Correct 223 ms 66660 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8160 KB Output is correct
2 Correct 48 ms 6808 KB Output is correct
3 Correct 66 ms 7624 KB Output is correct
4 Correct 51 ms 6980 KB Output is correct
5 Correct 50 ms 6832 KB Output is correct
6 Correct 60 ms 7712 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 317 ms 106092 KB Output is correct
9 Correct 284 ms 105596 KB Output is correct
10 Correct 293 ms 102096 KB Output is correct
11 Correct 291 ms 97612 KB Output is correct
12 Correct 307 ms 127032 KB Output is correct
13 Correct 316 ms 129136 KB Output is correct
14 Correct 219 ms 11540 KB Output is correct
15 Correct 342 ms 82028 KB Output is correct
16 Correct 317 ms 70644 KB Output is correct
17 Correct 223 ms 66660 KB Output is correct
18 Correct 66 ms 8160 KB Output is correct
19 Correct 48 ms 6808 KB Output is correct
20 Correct 66 ms 7624 KB Output is correct
21 Correct 51 ms 6980 KB Output is correct
22 Correct 50 ms 6832 KB Output is correct
23 Correct 60 ms 7712 KB Output is correct
24 Correct 293 ms 93692 KB Output is correct
25 Correct 320 ms 95928 KB Output is correct
26 Correct 282 ms 92248 KB Output is correct
27 Correct 289 ms 86524 KB Output is correct
28 Correct 346 ms 31304 KB Output is correct
29 Correct 220 ms 16104 KB Output is correct