oj.uz

Submission #442050

# Submission time Handle Problem Language Result Execution time Memory
442050 2021-07-06T23:26:30 Z zaneyu Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 331 ms 276908 KB 
/*input
3 3
AA
AA
AGA
AA AA
AG GA
AG GA
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=1e18+1;
const int INF=0x3f3f3f3f;
int MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-3;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
inline ll mult(ll a,ll b){
    if(a>=MOD) a%=MOD;
    if(b>=MOD) b%=MOD;
    return (a*b)%MOD;
}
inline ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
const int maxn=2e6+5;
const int maxlg=__lg(maxn)+2;
string asd="ACGU";
int get(char x){
    REP(i,4) if(asd[i]==x) return i;
}
struct trie{
    vector<int> v[maxn];
    int arr[maxn][4];
    int cnt=1;
    int search(string s){
        int cur=0;
        REP(i,sz(s)){
            int z=get(s[i]);
            if(!arr[cur][z]){
                return -1;
            }
            cur=arr[cur][z];
        }
        return cur;
    }
    void insert(string s,int idx){
        int cur=0;
        REP(i,sz(s)){
            int z=get(s[i]);
            if(!arr[cur][z]) arr[cur][z]=cnt++;
            cur=arr[cur][z];
            v[cur].pb(idx);
        }
    }
}orig,rev;
string arr[maxn];
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,q;
    cin>>n>>q;
    REP(i,n) cin>>arr[i];
    sort(arr,arr+n);
    REP(i,n){
        orig.insert(arr[i],i);
        reverse(ALL(arr[i]));
        rev.insert(arr[i],i);
    }
    while(q--){
        string a,b;
        cin>>a>>b;
        reverse(ALL(b));
        int x=orig.search(a),y=rev.search(b);
        if(x==-1 or y==-1){
            cout<<"0\n";
            continue;
        }
        assert(sz(orig.v[x]));
        int l=orig.v[x][0],r=orig.v[x].back();
        cout<<upper_bound(ALL(rev.v[y]),r)-lower_bound(ALL(rev.v[y]),l)<<'\n';
    }
}

Compilation message

selling_rna.cpp: In function 'int get(char)':
selling_rna.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
   58 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 156868 KB Output is correct
2 Correct 83 ms 156872 KB Output is correct
3 Correct 85 ms 156796 KB Output is correct
4 Correct 85 ms 156824 KB Output is correct
5 Correct 85 ms 156836 KB Output is correct
6 Correct 84 ms 156824 KB Output is correct
7 Correct 87 ms 156868 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 264672 KB Output is correct
2 Correct 324 ms 261120 KB Output is correct
3 Correct 291 ms 265004 KB Output is correct
4 Correct 299 ms 260316 KB Output is correct
5 Correct 315 ms 275144 KB Output is correct
6 Correct 315 ms 276908 KB Output is correct
7 Correct 160 ms 180780 KB Output is correct
8 Correct 330 ms 244056 KB Output is correct
9 Correct 275 ms 231944 KB Output is correct
10 Correct 252 ms 228512 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 158276 KB Output is correct
2 Correct 106 ms 158212 KB Output is correct
3 Correct 115 ms 158152 KB Output is correct
4 Correct 106 ms 158084 KB Output is correct
5 Correct 108 ms 158212 KB Output is correct
6 Correct 113 ms 158096 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 156868 KB Output is correct
2 Correct 83 ms 156872 KB Output is correct
3 Correct 85 ms 156796 KB Output is correct
4 Correct 85 ms 156824 KB Output is correct
5 Correct 85 ms 156836 KB Output is correct
6 Correct 84 ms 156824 KB Output is correct
7 Correct 87 ms 156868 KB Output is correct
8 Correct 331 ms 264672 KB Output is correct
9 Correct 324 ms 261120 KB Output is correct
10 Correct 291 ms 265004 KB Output is correct
11 Correct 299 ms 260316 KB Output is correct
12 Correct 315 ms 275144 KB Output is correct
13 Correct 315 ms 276908 KB Output is correct
14 Correct 160 ms 180780 KB Output is correct
15 Correct 330 ms 244056 KB Output is correct
16 Correct 275 ms 231944 KB Output is correct
17 Correct 252 ms 228512 KB Output is correct
18 Correct 112 ms 158276 KB Output is correct
19 Correct 106 ms 158212 KB Output is correct
20 Correct 115 ms 158152 KB Output is correct
21 Correct 106 ms 158084 KB Output is correct
22 Correct 108 ms 158212 KB Output is correct
23 Correct 113 ms 158096 KB Output is correct
24 Correct 318 ms 248880 KB Output is correct
25 Correct 329 ms 248900 KB Output is correct
26 Correct 310 ms 247824 KB Output is correct
27 Correct 299 ms 247624 KB Output is correct
28 Correct 291 ms 190864 KB Output is correct
29 Correct 181 ms 170040 KB Output is correct