oj.uz

Submission #1091355

# Submission time Handle Problem Language Result Execution time Memory
1091355 2024-09-20T16:43:28 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 45 ms 54732 KB 

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=(j);i>=(k);i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+6;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=123456789;

int n,m;

int node[maxn][4],Time;
vector<int> L[maxn];
string s[maxn];
void Transform(string& s)
{
    for(char& c:s)
    {
        if (c=='U') c='B';
        else if (c=='G') c='D';
    }
}
void sol()
{
    cin >> n>> m;
    for1(i,1,n)
    {
        cin >> s[i];
        Transform(s[i]);
    }
    memset(node,-1,sizeof(node));
    sort(s+1,s+1+n);
    for1(i,1,n)
    {
        int cur=0;
        string x=s[i];
        reverse(all(x));
        for(char c:x)
        {
            if (node[cur][c-'A']==-1) node[cur][c-'A']=++Time;
            cur=node[cur][c-'A'];
            L[cur].pb(i);
        }
    }
    for1(i,1,m)
    {
        string p,q;
        cin>>p>>q;
        Transform(p);
        Transform(q);
        int l=lower_bound(s+1,s+1+n,p)-s;
        p.back()++;
        int r=lower_bound(s+1,s+1+n,p)-s-1;
        if (r<l)
        {
            cout << "0\n";
            continue;
        }
        reverse(all(q));
        int cur=0;
        for(char c:q)
        {
            cur=node[cur][c-'A'];
            if (cur==-1) break;
        }
        if (cur==-1)
        {
            cout << "0\n";
            continue;
        }
        cout << upper_bound(all(L[cur]),r)-lower_bound(all(L[cur]),l)<<'\n';
    }

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("PAINT.inp","r",stdin);
//    freopen("PAINT.out","w",stdout);
    int t=1;//cin>>t;
    while (t--)
    {
        sol();
    }
}
/*
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 54732 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19284 KB Output is correct
2 Correct 25 ms 19036 KB Output is correct
3 Correct 30 ms 19292 KB Output is correct
4 Correct 31 ms 19152 KB Output is correct
5 Correct 25 ms 19160 KB Output is correct
6 Correct 28 ms 19156 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17496 KB Output is correct
2 Correct 8 ms 17500 KB Output is correct
3 Correct 8 ms 17684 KB Output is correct
4 Correct 7 ms 17496 KB Output is correct
5 Correct 8 ms 17500 KB Output is correct
6 Correct 7 ms 17500 KB Output is correct
7 Correct 7 ms 17500 KB Output is correct
8 Runtime error 45 ms 54732 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -