Submission #866792

#	Time	Username	Problem	Language	Result	Execution time	Memory
866792		catlover	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	258 ms	297940 KiB

selling_rna

// 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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40