oj.uz

Submission #362507

# Submission time Handle Problem Language Result Execution time Memory
362507 2021-02-03T12:45:13 Z denkendoemeer Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 652 ms 345964 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define rit string::reverse_iterator
ll n,m;
struct tri
{
    map<char,tri*>ch;
    vector<ll>ind;
    void insert(rit st,rit dr,ll poz)
    {
        ind.push_back(poz);
        if (st==dr)
            return ;
        char cha=*st;
        if (ch.find(cha)==ch.end())
            ch[cha]=new tri();
        ch[cha]->insert(next(st),dr,poz);
    }
    ll cnt(rit st,rit dr,ll l,ll r)
    {
        if (st==dr)
            return lower_bound(ind.begin(),ind.end(),r)-lower_bound(ind.begin(),ind.end(),l);
        char cha=*st;
        if (ch.find(cha)==ch.end())
            return 0;
        return ch[cha]->cnt(next(st),dr,l,r);
    }
}trie;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%lld%lld\n",&n,&m);
    vector<string>s(n);
    ll i;
    for(i=0;i<n;i++)
        cin>>s[i];
    sort(s.begin(),s.end());
    for(i=0;i<n;i++)
        trie.insert(s[i].rbegin(),s[i].rend(),i);
    while(m--){
        string x,y;
        cin>>x>>y;
        ll st=lower_bound(s.begin(),s.end(),x)-s.begin();
        ++x.back();
        ll dr=lower_bound(s.begin(),s.end(),x)-s.begin();
        printf("%lld\n",trie.cnt(y.rbegin(),y.rend(),st,dr));
    }
return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     scanf("%lld%lld\n",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 345964 KB Output is correct
2 Correct 532 ms 327788 KB Output is correct
3 Correct 244 ms 30060 KB Output is correct
4 Correct 244 ms 29036 KB Output is correct
5 Correct 375 ms 214508 KB Output is correct
6 Correct 378 ms 217748 KB Output is correct
7 Correct 266 ms 24172 KB Output is correct
8 Correct 456 ms 143852 KB Output is correct
9 Correct 420 ms 125292 KB Output is correct
10 Correct 291 ms 117868 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 4192 KB Output is correct
2 Correct 114 ms 3692 KB Output is correct
3 Correct 147 ms 3940 KB Output is correct
4 Correct 121 ms 3304 KB Output is correct
5 Correct 115 ms 3304 KB Output is correct
6 Correct 151 ms 3724 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 557 ms 345964 KB Output is correct
9 Correct 532 ms 327788 KB Output is correct
10 Correct 244 ms 30060 KB Output is correct
11 Correct 244 ms 29036 KB Output is correct
12 Correct 375 ms 214508 KB Output is correct
13 Correct 378 ms 217748 KB Output is correct
14 Correct 266 ms 24172 KB Output is correct
15 Correct 456 ms 143852 KB Output is correct
16 Correct 420 ms 125292 KB Output is correct
17 Correct 291 ms 117868 KB Output is correct
18 Correct 170 ms 4192 KB Output is correct
19 Correct 114 ms 3692 KB Output is correct
20 Correct 147 ms 3940 KB Output is correct
21 Correct 121 ms 3304 KB Output is correct
22 Correct 115 ms 3304 KB Output is correct
23 Correct 151 ms 3724 KB Output is correct
24 Correct 554 ms 285180 KB Output is correct
25 Correct 652 ms 285184 KB Output is correct
26 Correct 516 ms 281836 KB Output is correct
27 Correct 298 ms 29036 KB Output is correct
28 Correct 640 ms 65748 KB Output is correct
29 Correct 465 ms 17492 KB Output is correct