Submission #868403

#	Time	Username	Problem	Language	Result	Execution time	Memory
868403		cpptowin	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	249 ms	194288 KiB

selling_rna

#include<bits/stdc++.h>
#define name "TASK"
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 100010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
//#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
int convert(char t)
{
    if(t == 'A') return 0;
    if(t == 'U') return 1;
    if(t == 'G') return 2;
    if(t == 'C') return 3;
}
namespace Trie
{
struct node
{
    node *child[4];
    pii range;
    node()
    {
        memset(child,0,sizeof child);
        range = {-1,-1};
    }
};
node *root = new node();
void add(string s,int id)
{
    node *p = root;
    for(char c : s)
    {
        if(p -> child[convert(c)] == NULL) p -> child[convert(c)] = new node();
        p = p -> child[convert(c)];
        if(p -> range.fi == -1) p -> range = {id,id};
        else p -> range.se = id;
    }
}
pii get(string s)
{
    node *p = root;
    for(char c : s)
    {
        if(p -> child[convert(c)] == NULL) return {-1,-1};
        p = p -> child[convert(c)];
    }
    return p -> range;
}
}
namespace RevTrie
{
struct node
{
    node *child[4];
    vi save;
    node()
    {
        memset(child,0,sizeof child);
    }
};
node *root = new node();
void add(string s,int id)
{
    node *p = root;
    for(int i = s.size() - 1 ; i >= 0 ; i--)
    {
        if(p -> child[convert(s[i])] == NULL) p -> child[convert(s[i])] = new node();
        p = p -> child[convert(s[i])];
        p ->save.pb(id);
    }
}
vi get(string s)
{
    node *p = root;
    vi v;
    for(int i = s.size() - 1 ; i >= 0 ; i--)
    {
        if(p -> child[convert(s[i])] == NULL) return v;
        p = p -> child[convert(s[i])];
    }
    return p -> save;
}
}
string s[maxn];
int n;
string p,q;
int t;
main()
{
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> t;
    fo(i,1,n) cin >> s[i];
    sort(s + 1,s+ n + 1);
    fo(i,1,n)
    {
        Trie::add(s[i],i);
        RevTrie::add(s[i],i);
    }
    while(t--)
    {
        cin >> p >> q;
        pii range = Trie::get(p);
        vi v = RevTrie::get(q);
        if(v.size() == 0 or range.fi == -1) cout << 0 << "\n";
        else
        {
            int lb = lower_bound(v.begin(),v.end(),range.fi) - v.begin();
            int ub = upper_bound(v.begin(),v.end(),range.se) - v.begin() - 1;
            cout << (ub - lb + 1) << "\n";
        }
    }
}

Compilation message (stderr)

selling_rna.cpp:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  119 | main()
      | ^~~~
selling_rna.cpp: In function 'int convert(char)':
selling_rna.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40