oj.uz

Submission #240713

# Submission time Handle Problem Language Result Execution time Memory
240713 2020-06-20T22:00:03 Z aggu_01000101 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 998 ms 138204 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define INF 100000000000000000
#define int long long
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
const int N = 1e5 + 5;
int n, m;
vector<string> v;
vector<string> v1;
vector<string> mst[(int)4*N];
string reverse(string s){
    string tr = "";
    for(int i = s.length()-1;i>=0;i--) tr+=s[i];
    return tr;
}
void build(int l ,int u, int i){
    if(l==u){
        mst[i].push_back(v1[l]);
        return;
    }
    build(l, mid(l, u), lchild(i));
    build(mid(l,u)+1, u, rchild(i));
    merge(mst[lchild(i)].begin(), mst[lchild(i)].end(), mst[rchild(i)].begin(), mst[rchild(i)].end(), back_inserter(mst[i]));
}
int query(int l, int u, int i, int ll, int uu, const string& s, const string& s1){
    if(l>=ll && u<=uu){
        //cout<<"RANGE "<<l<<" "<<u<<endl;
        //cout<<s1<<" "<<s<<endl;
        //cout<<mst[i][(lower_bound(mst[i].begin(), mst[i].end(), s1) - mst[i].begin())]<<" "<<mst[i][(lower_bound(mst[i].begin(), mst[i].end(), s) - mst[i].begin())]<<endl;
        int ans = (lower_bound(mst[i].begin(), mst[i].end(), s1) - lower_bound(mst[i].begin(), mst[i].end(), s));
        return ans;
    }
    if(l>uu || u<ll) return 0;
    return query(l, mid(l, u), lchild(i), ll, uu, s, s1) + query(mid(l, u)+1, u, rchild(i), ll, uu, s, s1);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i = 0;i<n;i++){
        string s;
        cin>>s;
        v.push_back(s);
    }
    sort(v.begin(), v.end());
    for(int i = 0;i<n;i++){
        v1.push_back(reverse(v[i]));
    }
    build(0, n-1, 0);
    while(m--){
        string p, q;
        cin>>p>>q;
        q = reverse(q);
        string tempp = p;
        string tempq = q;
        tempp[p.size()-1]++;
        tempq[q.size()-1]++;
        int begind = lower_bound(v.begin(), v.end(), p) - v.begin();
        int endind = lower_bound(v.begin(), v.end(), tempp) - v.begin() - 1;
        //cout<<begind<<" "<<endind<<endl;
        if(begind <= endind) cout<<query(0, n-1, 0, begind, endind, q, tempq)<<"\n";
        else cout<<0<<"\n";
    }
}
/*
8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA
 */

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9856 KB Output is correct
2 Correct 12 ms 9728 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 10 ms 9856 KB Output is correct
5 Correct 12 ms 9728 KB Output is correct
6 Correct 11 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 43360 KB Output is correct
2 Correct 99 ms 48976 KB Output is correct
3 Correct 97 ms 45944 KB Output is correct
4 Correct 119 ms 49012 KB Output is correct
5 Correct 73 ms 35868 KB Output is correct
6 Correct 73 ms 36212 KB Output is correct
7 Correct 79 ms 37368 KB Output is correct
8 Correct 94 ms 50676 KB Output is correct
9 Correct 97 ms 50676 KB Output is correct
10 Correct 84 ms 48244 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 47976 KB Output is correct
2 Correct 151 ms 30064 KB Output is correct
3 Correct 187 ms 42840 KB Output is correct
4 Correct 115 ms 36584 KB Output is correct
5 Correct 111 ms 30064 KB Output is correct
6 Correct 157 ms 42724 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9856 KB Output is correct
2 Correct 12 ms 9728 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 10 ms 9856 KB Output is correct
5 Correct 12 ms 9728 KB Output is correct
6 Correct 11 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 63 ms 43360 KB Output is correct
9 Correct 99 ms 48976 KB Output is correct
10 Correct 97 ms 45944 KB Output is correct
11 Correct 119 ms 49012 KB Output is correct
12 Correct 73 ms 35868 KB Output is correct
13 Correct 73 ms 36212 KB Output is correct
14 Correct 79 ms 37368 KB Output is correct
15 Correct 94 ms 50676 KB Output is correct
16 Correct 97 ms 50676 KB Output is correct
17 Correct 84 ms 48244 KB Output is correct
18 Correct 159 ms 47976 KB Output is correct
19 Correct 151 ms 30064 KB Output is correct
20 Correct 187 ms 42840 KB Output is correct
21 Correct 115 ms 36584 KB Output is correct
22 Correct 111 ms 30064 KB Output is correct
23 Correct 157 ms 42724 KB Output is correct
24 Correct 208 ms 55824 KB Output is correct
25 Correct 326 ms 55916 KB Output is correct
26 Correct 161 ms 55664 KB Output is correct
27 Correct 196 ms 55916 KB Output is correct
28 Correct 998 ms 138204 KB Output is correct
29 Correct 444 ms 91736 KB Output is correct