oj.uz

Submission #866931

# Submission time Handle Problem Language Result Execution time Memory
866931 2023-10-27T12:12:39 Z catlover Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 287 ms 300144 KB 
// cre: Nguyen Hoang Hung - Train VOI 2024

#include <bits/stdc++.h>

#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 convert(char c)
{
    if(c == 'A') return 0;
    if(c == 'U') return 1;
    if(c == 'G') return 2;
    return 3;
}

/////////////////////////////////////////////////////////
/**
    BUILD TRIE
**/

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

int pos[maxN+5];

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

void rev_add(string s, int id)
{
    Trie *p = &rev_T;
    for(int i = 0; i < SZ(s); ++i)
    {
        int c = convert(s[i]);
        if(p->ch[c] == NULL) p->ch[c] = new Trie;
        p = p->ch[c];
        p->vt.pb(pos[id]);
    }
}

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

int Time = 0;

void dfs(Trie *p)
{
    p->tin = ++Time;
    if(SZ(p->vt) > 0)
    {
        for(int x : p->vt)
        pos[x] = Time;
    }
    FOR(i, 0, 3)
        if(p->ch[i] != NULL) dfs(p->ch[i]);
    p->tout = Time;
}

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

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

int getAns(string s, pii Range)
{
    Trie *p = &rev_T;
    for(int i = 0; i < SZ(s); ++i)
    {
        int c = convert(s[i]);
        if(p->ch[c] == NULL) return 0;
        p = p->ch[c];
    }
    int le = lower_bound(all(p->vt), Range.fi) - p->vt.begin();
    int ri = upper_bound(all(p->vt), Range.se) - p->vt.begin() - 1;
    return ri - le + 1;
}

string s[maxN+5];

void solve() {
    int N, M;   cin >> N >> M;
    FOR(i, 1, N)
    {
        cin >> s[i];
        add(s[i], i);
        reverse(all(s[i]));
    }
    dfs(&T);
    FOR(i, 1, N)
    {
        rev_add(s[i], i);
    }
    dfs_rev(&rev_T);
    while(M --> 0)
    {
        string P, Q;
        cin >> P >> Q;
        reverse(all(Q));
        pii Range = getRange(P);
//        cout << Range.fi << ' ' << Range.se << endl;
        cout << getAns(Q, Range) << '\n';
    }
}

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

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

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

    file("test_code");

//    solve_TestCase();

    solve();

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

    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 284064 KB Output is correct
2 Correct 240 ms 274772 KB Output is correct
3 Correct 233 ms 234152 KB Output is correct
4 Correct 238 ms 226136 KB Output is correct
5 Correct 287 ms 296576 KB Output is correct
6 Correct 268 ms 300144 KB Output is correct
7 Correct 67 ms 80004 KB Output is correct
8 Correct 239 ms 212052 KB Output is correct
9 Correct 216 ms 190036 KB Output is correct
10 Correct 182 ms 184648 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 65508 KB Output is correct
2 Correct 27 ms 65928 KB Output is correct
3 Correct 28 ms 65872 KB Output is correct
4 Correct 24 ms 65372 KB Output is correct
5 Correct 28 ms 65872 KB Output is correct
6 Correct 30 ms 65628 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 64092 KB Output is correct
2 Correct 13 ms 64092 KB Output is correct
3 Correct 13 ms 64088 KB Output is correct
4 Correct 13 ms 64184 KB Output is correct
5 Correct 13 ms 64092 KB Output is correct
6 Correct 13 ms 64092 KB Output is correct
7 Correct 13 ms 64092 KB Output is correct
8 Correct 241 ms 284064 KB Output is correct
9 Correct 240 ms 274772 KB Output is correct
10 Correct 233 ms 234152 KB Output is correct
11 Correct 238 ms 226136 KB Output is correct
12 Correct 287 ms 296576 KB Output is correct
13 Correct 268 ms 300144 KB Output is correct
14 Correct 67 ms 80004 KB Output is correct
15 Correct 239 ms 212052 KB Output is correct
16 Correct 216 ms 190036 KB Output is correct
17 Correct 182 ms 184648 KB Output is correct
18 Correct 29 ms 65508 KB Output is correct
19 Correct 27 ms 65928 KB Output is correct
20 Correct 28 ms 65872 KB Output is correct
21 Correct 24 ms 65372 KB Output is correct
22 Correct 28 ms 65872 KB Output is correct
23 Correct 30 ms 65628 KB Output is correct
24 Correct 214 ms 246960 KB Output is correct
25 Correct 233 ms 247088 KB Output is correct
26 Correct 216 ms 244804 KB Output is correct
27 Correct 237 ms 205744 KB Output is correct
28 Correct 155 ms 103836 KB Output is correct
29 Correct 74 ms 73112 KB Output is correct