oj.uz

Submission #729971

# Submission time Handle Problem Language Result Execution time Memory
729971 2023-04-25T01:19:46 Z n0sk1ll Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 217 ms 155992 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

const int N=6'000'006;

struct pers_segtree
{
    int val[N],L[N],R[N];
    int idx=0;

    int root[200005];

    //root se podrazumeva da je kec (1)

    void add(int p, int q, int l, int r, int s, int x)
    {
        val[p]=val[q]+x;
        if (l==r) return;
        int mid=(l+r)/2;
        if (s<=mid) L[p]=++idx,R[p]=R[q],add(L[p],L[q],l,mid,s,x);
        else L[p]=L[q],R[p]=++idx,add(R[p],R[q],mid+1,r,s,x);
    }

    int sum(int p, int q, int l, int r, int ll, int rr)
    {
        if (ll>r || rr<l) return 0;
        if (ll<=l && rr>=r) return val[p]-val[q];
        int mid=(l+r)/2;
        return sum(L[p],L[q],l,mid,ll,rr)+sum(R[p],R[q],mid+1,r,ll,rr);
    }
} ST;

struct nicetrie
{
    int idx=1;
    int node[2000006][4];
    vector<int> inds[2000006];
    int tin[2000006],tout[2000006];
    int perm[2000006];

    //root se podrazumeva da je kec (1)

    void add(string &s, int ind)
    {
        int p=1;

        for (auto c : s)
        {
            int gde;
            if (c=='A') gde=0;
            else if (c=='C') gde=1;
            else if (c=='G') gde=2;
            else gde=3;

            if (!node[p][gde]) node[p][gde]=++idx;
            p=node[p][gde];
        }

        inds[p].pb(ind);
    }

    int VREME=1;
    void dfs(int p)
    {
        tin[p]=VREME;
        for (auto it : inds[p]) perm[VREME++]=it;
        ff(i,0,4) if (node[p][i]) dfs(node[p][i]);
        tout[p]=VREME;
    }

    pii le_find(string &s)
    {
        int p=1;

        for (auto c : s)
        {
            int gde;
            if (c=='A') gde=0;
            else if (c=='C') gde=1;
            else if (c=='G') gde=2;
            else gde=3;

            p=node[p][gde];
            if (!p) return {-1,-1};
        }

        return {tin[p],tout[p]-1};
    }
} pref, suf;

int gdeusuf[200005];
int sami[200005];

int main()
{
    FAST;

    int n,q; cin>>n>>q;
    fff(i,1,n)
    {
        string s; cin>>s;
        pref.add(s,i);

        reverse(all(s));
        suf.add(s,i);
    }

    pref.dfs(1);
    suf.dfs(1);

    fff(i,1,n) gdeusuf[suf.perm[i]]=i;
    fff(i,1,n) sami[i]=gdeusuf[pref.perm[i]];

    ST.root[0]=++ST.idx;
    fff(i,1,n)
    {
        ST.root[i]=++ST.idx;
        ST.add(ST.root[i],ST.root[i-1],1,n,sami[i],1);
    }

    while (q--)
    {
        string a,b; cin>>a>>b; reverse(all(b));
        auto [l1,r1]=pref.le_find(a);
        auto [l2,r2]=suf.le_find(b);

        //cout<<"["<<l1<<","<<r1<<"] x ["<<l2<<","<<r2<<"]: ";
        if (l1>r1 || l2>r2 || l1==-1 || l2==-1 || r1==-1 || r2==-1) cout<<0<<"\n";
        else cout<<ST.sum(ST.root[r1],ST.root[l1-1],1,n,l2,r2)<<"\n";
    }
}

//Note to self: Check for overflow

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 94272 KB Output is correct
2 Correct 49 ms 94256 KB Output is correct
3 Correct 49 ms 94284 KB Output is correct
4 Correct 49 ms 94312 KB Output is correct
5 Correct 47 ms 94372 KB Output is correct
6 Correct 56 ms 94364 KB Output is correct
7 Correct 54 ms 94324 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 145096 KB Output is correct
2 Correct 163 ms 143304 KB Output is correct
3 Correct 164 ms 144716 KB Output is correct
4 Correct 156 ms 142844 KB Output is correct
5 Correct 210 ms 155084 KB Output is correct
6 Correct 202 ms 155992 KB Output is correct
7 Correct 81 ms 100204 KB Output is correct
8 Correct 137 ms 134956 KB Output is correct
9 Correct 124 ms 129356 KB Output is correct
10 Correct 108 ms 126044 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 106400 KB Output is correct
2 Correct 67 ms 101420 KB Output is correct
3 Correct 71 ms 103880 KB Output is correct
4 Correct 68 ms 102028 KB Output is correct
5 Correct 65 ms 101500 KB Output is correct
6 Correct 74 ms 103868 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 94272 KB Output is correct
2 Correct 49 ms 94256 KB Output is correct
3 Correct 49 ms 94284 KB Output is correct
4 Correct 49 ms 94312 KB Output is correct
5 Correct 47 ms 94372 KB Output is correct
6 Correct 56 ms 94364 KB Output is correct
7 Correct 54 ms 94324 KB Output is correct
8 Correct 173 ms 145096 KB Output is correct
9 Correct 163 ms 143304 KB Output is correct
10 Correct 164 ms 144716 KB Output is correct
11 Correct 156 ms 142844 KB Output is correct
12 Correct 210 ms 155084 KB Output is correct
13 Correct 202 ms 155992 KB Output is correct
14 Correct 81 ms 100204 KB Output is correct
15 Correct 137 ms 134956 KB Output is correct
16 Correct 124 ms 129356 KB Output is correct
17 Correct 108 ms 126044 KB Output is correct
18 Correct 85 ms 106400 KB Output is correct
19 Correct 67 ms 101420 KB Output is correct
20 Correct 71 ms 103880 KB Output is correct
21 Correct 68 ms 102028 KB Output is correct
22 Correct 65 ms 101500 KB Output is correct
23 Correct 74 ms 103868 KB Output is correct
24 Correct 166 ms 138420 KB Output is correct
25 Correct 155 ms 138660 KB Output is correct
26 Correct 156 ms 137940 KB Output is correct
27 Correct 158 ms 138012 KB Output is correct
28 Correct 217 ms 128280 KB Output is correct
29 Correct 136 ms 121832 KB Output is correct