oj.uz

Submission #295186

# Submission time Handle Problem Language Result Execution time Memory
295186 2020-09-09T14:10:57 Z arman_ferdous Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 321 ms 296780 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define dbg(x) cerr << #x << " is " << x << "\n";

using ll = long long;
using ii = pair<ll,ll>;

const int N = 1e5+10;
const int M = 5e6+10;

int n, m;
char s[N];

char ID(char x) {
  if(x == 'A') return 'a';
  if(x == 'C') return 'b';
  if(x == 'G') return 'c';
  return 'd';
}

struct Trie{
  int node, to[4][M];
  vector<int> ending[M];

  Trie() { node = 1; }

  void insert(int len, int id) {
    int cur = 1;
    for(int i = 0; i < len; i++) {
      int val = ID(s[i]) - 'a';
      if(to[val][cur] == 0) to[val][cur] = ++node;
      assert(node < M);
      cur = to[val][cur];
    }
    ending[cur].push_back(id);
  }

  int in[M], out[M];
  vector<int> eul;
  void dfs(int u) {
    in[u] = eul.size();
    for(int x : ending[u]) eul.push_back(x);
    for(int v = 0; v < 4; v++) if(to[v][u] != 0)
      dfs(to[v][u]);
    out[u] = eul.size() - 1;
  }

  void find(int &l, int &r) {
    int cur = 1, len = strlen(s);
    for(int i = 0; i < len; i++) {
      int val = ID(s[i]) - 'a';
      if(to[val][cur] == 0) {
        l = r = -1;
        return;
      } cur = to[val][cur];
    }
    l = in[cur], r = out[cur];
  }
}trie, eirt;

int result[N];
struct CPR{
  struct data{
    int x, y1, y2;
    int ty, id;
    // point = 0, [ = -1, ] = 1
    bool operator<(data o) const {
      if(x == o.x) return ty < o.ty;
      return x < o.x;
    }
  };
  vector<data> v;

  void insert_point(int x, int y) {
    x++, y++;
    v.push_back({x, y, 0, 0, 0});
  }
  void insert_rect(int x1, int x2, int y1, int y2, int id) {
    x1++, y1++, x2++, y2++;
    v.push_back({x1, y1, y2, -1, id});
    v.push_back({x2, y1, y2, +1, id});
  }

  int bit[N];
  void upd(int pos, int x) {
    while(pos < N) bit[pos] += x, pos += pos&-pos;
  }
  int get(int pos, int r = 0) {
    while(pos > 0) r += bit[pos], pos -= pos&-pos;
    return r;
  }

  void sweep() {
    sort(all(v));
    for(auto d : v) {
      if(d.ty == 0) upd(d.y1, +1);
      else result[d.id] += d.ty * (get(d.y2) - get(d.y1 - 1));
    }
  }
}ds;

int mp[M];

int main() {
  scanf("%d %d", &n, &m);
  for(int i = 0; i < n; i++) {
    scanf(" %s", s);
    int len = strlen(s);
    trie.insert(len, i);
    reverse(s, s + len);
    eirt.insert(len, i);
  }
  trie.dfs(1); eirt.dfs(1);
  for(int i = 0; i < n; i++) mp[trie.eul[i]] = i;
  for(int i = 0; i < n; i++) {
    eirt.eul[i] = mp[eirt.eul[i]];
    ds.insert_point(i, eirt.eul[i]);
  }
  for(int i = 0; i < m; i++) {
    scanf(" %s", s);
    int l, r; trie.find(l, r);

    scanf(" %s", s);
    reverse(s, s + strlen(s));
    int L, R; eirt.find(L, R);

    if(l != -1 && L != -1 && l <= r && L <= R) ds.insert_rect(L, R, l, r, i);
  }
  ds.sweep();
  for(int i = 0; i < m; i++)
    printf("%d\n", result[i]);
  return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |     scanf(" %s", s);
      |     ~~~~~^~~~~~~~~~
selling_rna.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |     scanf(" %s", s);
      |     ~~~~~^~~~~~~~~~
selling_rna.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  129 |     scanf(" %s", s);
      |     ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 235260 KB Output is correct
2 Correct 151 ms 235408 KB Output is correct
3 Correct 154 ms 235256 KB Output is correct
4 Correct 154 ms 235260 KB Output is correct
5 Correct 152 ms 235256 KB Output is correct
6 Correct 154 ms 235256 KB Output is correct
7 Correct 155 ms 235256 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 286300 KB Output is correct
2 Correct 276 ms 283976 KB Output is correct
3 Correct 299 ms 285888 KB Output is correct
4 Correct 283 ms 283596 KB Output is correct
5 Correct 312 ms 295880 KB Output is correct
6 Correct 321 ms 296780 KB Output is correct
7 Correct 202 ms 241596 KB Output is correct
8 Correct 258 ms 262984 KB Output is correct
9 Correct 254 ms 265416 KB Output is correct
10 Correct 229 ms 261320 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 241972 KB Output is correct
2 Correct 181 ms 239104 KB Output is correct
3 Correct 191 ms 239652 KB Output is correct
4 Correct 180 ms 239016 KB Output is correct
5 Correct 183 ms 239244 KB Output is correct
6 Correct 187 ms 239556 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 235260 KB Output is correct
2 Correct 151 ms 235408 KB Output is correct
3 Correct 154 ms 235256 KB Output is correct
4 Correct 154 ms 235260 KB Output is correct
5 Correct 152 ms 235256 KB Output is correct
6 Correct 154 ms 235256 KB Output is correct
7 Correct 155 ms 235256 KB Output is correct
8 Correct 286 ms 286300 KB Output is correct
9 Correct 276 ms 283976 KB Output is correct
10 Correct 299 ms 285888 KB Output is correct
11 Correct 283 ms 283596 KB Output is correct
12 Correct 312 ms 295880 KB Output is correct
13 Correct 321 ms 296780 KB Output is correct
14 Correct 202 ms 241596 KB Output is correct
15 Correct 258 ms 262984 KB Output is correct
16 Correct 254 ms 265416 KB Output is correct
17 Correct 229 ms 261320 KB Output is correct
18 Correct 192 ms 241972 KB Output is correct
19 Correct 181 ms 239104 KB Output is correct
20 Correct 191 ms 239652 KB Output is correct
21 Correct 180 ms 239016 KB Output is correct
22 Correct 183 ms 239244 KB Output is correct
23 Correct 187 ms 239556 KB Output is correct
24 Correct 275 ms 279188 KB Output is correct
25 Correct 293 ms 280580 KB Output is correct
26 Correct 265 ms 278032 KB Output is correct
27 Correct 269 ms 278508 KB Output is correct
28 Correct 310 ms 257716 KB Output is correct
29 Correct 273 ms 251232 KB Output is correct