oj.uz

Submission #866792

# Submission time Handle Problem Language Result Execution time Memory
866792 2023-10-27T05:28:01 Z catlover Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 258 ms 297940 KB 
// cre: Nguyen Hoang Hung - Train VOI 2024

#include <bits/stdc++.h>

#define int long long

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a->begin()) it = a->begin(); it != a->end(); ++it)

#define debug(x) { cerr << #x << " = "; cerr << (x) << endl; }
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }

#define bit(X, i) ((X >> i) & 1)
#define cntbit(X) __builtin_popcountll(X)
#define fi first
#define se second
#define pb push_back
#define all(X) begin(X), end(X)
#define SZ(X) ((int)(X).size())
#define RR(X) X->resize(unique(all(X)) - begin(X))
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;

template <typename T>
bool maximize(T &x, T y)
{
  if(x < y)
    x = y;
  else
    return 0;
  return 1;
}
template <typename T>
bool minimize(T &x, T y)
{
  if(x > y)
    x = y;
  else
    return 0;
  return 1;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

ll Rand(ll l, ll r) { return l + rand() % (r - l + 1); }

const int maxN = 2e6;
const ll inf = 1e18+7;
const int MOD = 1e9 + 7;
const double PI = acos(-1);

/*
-------------------------------------------------------------------------------------
    END OF TEMPLATE
-------------------------------------------------------------------------------------
    Nguyen Hoang Hung - catlover
    Training for VOI24 gold medal
-------------------------------------------------------------------------------------
*/

int N, M, pos[maxN];
string s[maxN];

int convert(char c) {

  if(c == 'A') return 0;
  if(c == 'G') return 1;
  if(c == 'C') return 2;
  return 3;
}

//////////////////////////////////////////////////
/**
  BUILD TRIE
**/
struct Trie
{
    Trie *child[4];
    int tin, tout;
    vector<int> vt;
    Trie()
    {
        FOR(i, 0, 3) child[i] = NULL;
        tin = tout = 0;
        vt.resize(0);
    }
};
Trie T, T_rev;

void add(string s, int id)
{
    Trie *p = &T;
    FOR(i, 0, SZ(s)-1)
    {
        int c = convert(s[i]);
        if (p->child[c] == NULL) p->child[c] = new Trie();
        p = p->child[c];
    }
    p->vt.pb(id);
}

void add_rev(string s, int id)
{
    Trie *p = &T_rev;
    FOR(i, 0, SZ(s)-1)
    {
        int c = convert(s[i]);
        if (p->child[c] == NULL) p->child[c] = new Trie();
        p = p->child[c];
        p->vt.pb(pos[id]);
    }
}

//////////////////////////////////////////////////
/**
  EULER TOUR
**/

int Time = 0;

void dfs(Trie *p)
{
    p->tin = ++Time;
    if(p->vt.size())
    {
        for(auto x : p->vt)
            pos[x] = Time;
    }
    FOR(i, 0, 3)
    {
        if(p->child[i] == NULL) continue;
        dfs(p->child[i]);
    }
    p->tout = Time;
}

void dfs_Rev(Trie *p)
{
    sort(all(p->vt));
    FOR(i, 0, 3)
    {
        if (p->child[i] == NULL) continue;
        dfs_Rev(p->child[i]);
    }
}

pii getRange(string s)
{
    Trie *p = &T;
    FOR(i, 0, SZ(s)-1)
    {
        int c = convert(s[i]);
        if (p->child[c] == NULL) return make_pair(0, 0);
        p = p->child[c];
    }
    return make_pair(p->tin, p->tout);
}

int getAns(string s, pii Range)
{
    Trie *p = &T_rev;
    FOR(i, 0, SZ(s)-1)
    {
        int c = convert(s[i]);
        if (p->child[c] == NULL) return 0;
        p = p->child[c];
    }
    int l = lower_bound(all(p->vt), Range.fi) - p->vt.begin();
    int r = upper_bound(all(p->vt), Range.se) - p->vt.begin()-1;
    return (r - l + 1);
}

void solve() {

  cin >> N >> M;

  FOR(i, 1, N) cin >> s[i];
  FOR(i, 1, N) add(s[i], i);
  dfs(&T);

  FOR(i, 1, N) reverse(all(s[i]));
  FOR(i, 1, N) add_rev(s[i], i);
  dfs_Rev(&T_rev);

  while(M --> 0)
  {
      string P, Q; cin >> P >> Q;
      reverse(all(Q));
      pii R = getRange(P);
//      cout << R.fi << ' ' << R.se << endl;
      cout << getAns(Q, R) << '\n';
  }
}

void solve_TestCase() {
  int testcase; cin >> testcase;

  while(testcase --> 0)
  {
    solve();
  }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);

    file("RNA");

//    solve_TestCase();

    solve();

    cerr << "\nTime : " << clock()/1000.0 << "s\n";

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:24:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:213:5: note: in expansion of macro 'file'
  213 |     file("RNA");
      |     ^~~~
selling_rna.cpp:24:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:213:5: note: in expansion of macro 'file'
  213 |     file("RNA");
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 64092 KB Output is correct
2 Correct 12 ms 64092 KB Output is correct
3 Correct 12 ms 64092 KB Output is correct
4 Correct 12 ms 64088 KB Output is correct
5 Correct 12 ms 64092 KB Output is correct
6 Correct 12 ms 64116 KB Output is correct
7 Correct 13 ms 64424 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 282532 KB Output is correct
2 Correct 215 ms 270932 KB Output is correct
3 Correct 233 ms 240464 KB Output is correct
4 Correct 231 ms 233020 KB Output is correct
5 Correct 251 ms 294260 KB Output is correct
6 Correct 258 ms 297940 KB Output is correct
7 Correct 65 ms 82048 KB Output is correct
8 Correct 215 ms 212752 KB Output is correct
9 Correct 216 ms 191124 KB Output is correct
10 Correct 178 ms 187812 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 66004 KB Output is correct
2 Correct 27 ms 66268 KB Output is correct
3 Correct 29 ms 66264 KB Output is correct
4 Correct 24 ms 65880 KB Output is correct
5 Correct 27 ms 66172 KB Output is correct
6 Correct 35 ms 66500 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 64092 KB Output is correct
2 Correct 12 ms 64092 KB Output is correct
3 Correct 12 ms 64092 KB Output is correct
4 Correct 12 ms 64088 KB Output is correct
5 Correct 12 ms 64092 KB Output is correct
6 Correct 12 ms 64116 KB Output is correct
7 Correct 13 ms 64424 KB Output is correct
8 Correct 221 ms 282532 KB Output is correct
9 Correct 215 ms 270932 KB Output is correct
10 Correct 233 ms 240464 KB Output is correct
11 Correct 231 ms 233020 KB Output is correct
12 Correct 251 ms 294260 KB Output is correct
13 Correct 258 ms 297940 KB Output is correct
14 Correct 65 ms 82048 KB Output is correct
15 Correct 215 ms 212752 KB Output is correct
16 Correct 216 ms 191124 KB Output is correct
17 Correct 178 ms 187812 KB Output is correct
18 Correct 28 ms 66004 KB Output is correct
19 Correct 27 ms 66268 KB Output is correct
20 Correct 29 ms 66264 KB Output is correct
21 Correct 24 ms 65880 KB Output is correct
22 Correct 27 ms 66172 KB Output is correct
23 Correct 35 ms 66500 KB Output is correct
24 Correct 203 ms 244312 KB Output is correct
25 Correct 235 ms 244308 KB Output is correct
26 Correct 198 ms 242516 KB Output is correct
27 Correct 234 ms 212308 KB Output is correct
28 Correct 178 ms 110404 KB Output is correct
29 Correct 72 ms 74968 KB Output is correct