oj.uz

Submission #251480

# Submission time Handle Problem Language Result Execution time Memory
251480 2020-07-21T11:18:01 Z balbit Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 443 ms 257656 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2e6+5;

vector<vector<int> > a;
vector<pair<vector<int> , int> > que;
pii rng[maxn];

int to[maxn*2][4];
int lb[maxn*2], rb[maxn*2];
int trieat = 2;

int n,q;

map<char, int> mp = {{'A',0},{'G',1},{'C',2},{'U',3}};

vector<int> cv(string s) {
    vector<int> re(SZ(s));
    for (int i = 0; i<SZ(s); ++i) re[i] = mp[s[i]];
    return re;
}

vector<int> stuff[maxn*2];

int add(vector<int> s, int at, int id=-1, bool t1=1) {
    for (int i = 0; i<SZ(s); ++i) {
        if (to[at][s[i]] == -1) {
            to[at][s[i]] = trieat ++;
        }
        at = to[at][s[i]];
        if (t1 && id != -1) {
            lb[at] = min(lb[at], id);
            rb[at] = max(rb[at], id);
        }else if (t1 == 0){
            stuff[at].pb(id);
        }
    }
    return at;
}

signed main(){
    IOS();
    memset(to, -1, sizeof to);
    memset(lb, 0x3f, sizeof lb);
    memset(rb, -1, sizeof rb);
    cin>>n>>q;
    int root1 = 0, root2 = 1;
    for (int i = 0; i<n; ++i) {
        string s; cin>>s;
        a.pb(cv(s));
    }
    sort(ALL(a));
    for (int i = 0; i<n; ++i){
        add(a[i], 0, i);
        vector<int> tmp = a[i]; reverse(ALL(tmp));
        add(tmp, 1,i,0);
    }
    for (int i =0 ; i<trieat; ++i) {
        sort(ALL(stuff[i]));
    }
    for (int i = 0; i<q; ++i) {
        string a, b; cin>>a>>b;
        reverse(ALL(b));
        int tmp = add(cv(a),0);
        int L = lb[tmp], R = rb[tmp];
        bug(L,R);
        int n2 = add(cv(b), 1);
        bug(tmp, n2);
        int ans = (upper_bound(ALL(stuff[n2]), R) - stuff[n2].begin()) - 1
                - (upper_bound(ALL(stuff[n2]), L-1) - stuff[n2].begin() - 1);
        cout<<max(0,ans)<<endl;
    }

}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:92:9: warning: unused variable 'root1' [-Wunused-variable]
     int root1 = 0, root2 = 1;
         ^~~~~
selling_rna.cpp:92:20: warning: unused variable 'root2' [-Wunused-variable]
     int root1 = 0, root2 = 1;
                    ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188152 KB Output is correct
2 Correct 102 ms 188152 KB Output is correct
3 Correct 110 ms 188280 KB Output is correct
4 Correct 101 ms 188280 KB Output is correct
5 Correct 105 ms 188152 KB Output is correct
6 Correct 107 ms 188280 KB Output is correct
7 Correct 104 ms 188152 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 257656 KB Output is correct
2 Correct 393 ms 254620 KB Output is correct
3 Correct 247 ms 207864 KB Output is correct
4 Correct 251 ms 207736 KB Output is correct
5 Correct 282 ms 231672 KB Output is correct
6 Correct 287 ms 232440 KB Output is correct
7 Correct 214 ms 203128 KB Output is correct
8 Correct 315 ms 224632 KB Output is correct
9 Correct 300 ms 220664 KB Output is correct
10 Correct 267 ms 220152 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 191916 KB Output is correct
2 Correct 143 ms 190780 KB Output is correct
3 Correct 141 ms 191400 KB Output is correct
4 Correct 129 ms 190768 KB Output is correct
5 Correct 133 ms 190640 KB Output is correct
6 Correct 145 ms 191272 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188152 KB Output is correct
2 Correct 102 ms 188152 KB Output is correct
3 Correct 110 ms 188280 KB Output is correct
4 Correct 101 ms 188280 KB Output is correct
5 Correct 105 ms 188152 KB Output is correct
6 Correct 107 ms 188280 KB Output is correct
7 Correct 104 ms 188152 KB Output is correct
8 Correct 382 ms 257656 KB Output is correct
9 Correct 393 ms 254620 KB Output is correct
10 Correct 247 ms 207864 KB Output is correct
11 Correct 251 ms 207736 KB Output is correct
12 Correct 282 ms 231672 KB Output is correct
13 Correct 287 ms 232440 KB Output is correct
14 Correct 214 ms 203128 KB Output is correct
15 Correct 315 ms 224632 KB Output is correct
16 Correct 300 ms 220664 KB Output is correct
17 Correct 267 ms 220152 KB Output is correct
18 Correct 141 ms 191916 KB Output is correct
19 Correct 143 ms 190780 KB Output is correct
20 Correct 141 ms 191400 KB Output is correct
21 Correct 129 ms 190768 KB Output is correct
22 Correct 133 ms 190640 KB Output is correct
23 Correct 145 ms 191272 KB Output is correct
24 Correct 397 ms 247004 KB Output is correct
25 Correct 443 ms 247136 KB Output is correct
26 Correct 394 ms 246396 KB Output is correct
27 Correct 268 ms 207028 KB Output is correct
28 Correct 397 ms 215484 KB Output is correct
29 Correct 274 ms 200740 KB Output is correct