oj.uz

Submission #868403

# Submission time Handle Problem Language Result Execution time Memory
868403 2023-10-31T12:06:14 Z cpptowin Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 249 ms 194288 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3592 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 194288 KB Output is correct
2 Correct 188 ms 184312 KB Output is correct
3 Correct 108 ms 111952 KB Output is correct
4 Correct 105 ms 106984 KB Output is correct
5 Correct 167 ms 178656 KB Output is correct
6 Correct 169 ms 181436 KB Output is correct
7 Correct 37 ms 19028 KB Output is correct
8 Correct 141 ms 117848 KB Output is correct
9 Correct 120 ms 101336 KB Output is correct
10 Correct 93 ms 96100 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 4736 KB Output is correct
2 Correct 23 ms 4952 KB Output is correct
3 Correct 33 ms 4696 KB Output is correct
4 Correct 32 ms 4652 KB Output is correct
5 Correct 43 ms 4700 KB Output is correct
6 Correct 61 ms 4700 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3592 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 209 ms 194288 KB Output is correct
9 Correct 188 ms 184312 KB Output is correct
10 Correct 108 ms 111952 KB Output is correct
11 Correct 105 ms 106984 KB Output is correct
12 Correct 167 ms 178656 KB Output is correct
13 Correct 169 ms 181436 KB Output is correct
14 Correct 37 ms 19028 KB Output is correct
15 Correct 141 ms 117848 KB Output is correct
16 Correct 120 ms 101336 KB Output is correct
17 Correct 93 ms 96100 KB Output is correct
18 Correct 104 ms 4736 KB Output is correct
19 Correct 23 ms 4952 KB Output is correct
20 Correct 33 ms 4696 KB Output is correct
21 Correct 32 ms 4652 KB Output is correct
22 Correct 43 ms 4700 KB Output is correct
23 Correct 61 ms 4700 KB Output is correct
24 Correct 181 ms 160636 KB Output is correct
25 Correct 249 ms 160620 KB Output is correct
26 Correct 184 ms 158896 KB Output is correct
27 Correct 117 ms 94148 KB Output is correct
28 Correct 227 ms 38708 KB Output is correct
29 Correct 76 ms 12012 KB Output is correct