oj.uz

Submission #294179

# Submission time Handle Problem Language Result Execution time Memory
294179 2020-09-08T16:37:32 Z b00n0rp Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 597 ms 588920 KB 
#include<bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define FORD(i,a,b) for(int i = a; i >= b; i --)
#define vi vector<int>
#define pb push_back
#define all(v) v.begin(),v.end()

int n,q;

string s[200005];

struct node{
    vi pos;
    int to[26];
} trie1[2000005],trie2[2000005];

int SZ1 = 1,SZ2 = 1;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    REP(i,n) cin >> s[i];
    sort(s,s+n);
    REP(i,n){
        int cur = 1;
        REP(j,(int)s[i].length()){
            int let = s[i][j]-'A';
            if(!trie1[cur].to[let]) trie1[cur].to[let] = ++SZ1; 
            cur = trie1[cur].to[let];
            trie1[cur].pos.pb(i);
        }
        cur = 1;
        FORD(j,(int)s[i].length()-1,0){
            // cout << i << " " << j << endl;
            int let = s[i][j]-'A';
            if(!trie2[cur].to[let]) trie2[cur].to[let] = ++SZ2; 
            cur = trie2[cur].to[let];
            trie2[cur].pos.pb(i);
        }
    }
    REP(i,SZ2+1) sort(all(trie2[i].pos));
    REP(i,q){
        string s1,s2; cin >> s1 >> s2;
        int cur1 = 1,cur2 = 1;
        bool f = 0;
        REP(j,(int)s1.length()){
            int let = s1[j]-'A';
            if(!trie1[cur1].to[let]){
                f = 1;
                break;
            } 
            cur1 = trie1[cur1].to[let];
        }
        if(f){
            cout << "0\n";
            continue;
        }
        FORD(j,(int)s2.length()-1,0){
            int let = s2[j]-'A';
            if(!trie2[cur2].to[let]){
                f = 1;
                break;
            } 
            cur2 = trie2[cur2].to[let];
        }
        if(f){
            cout << "0\n";
            continue;
        }
        // cout << "-------------------------------\n";
        // cout << s1 << " - " << s2 << endl;
        // cout << trie1[cur1].pos.size() << endl;
        // for(auto x:trie1[cur1].pos) cout << x << " "; 
        // cout << endl;
        // cout << trie2[cur2].pos.size() << endl;
        // for(auto x:trie2[cur2].pos) cout << x << " "; 
        // cout << endl;
        // cout << "-------------------------------\n";
        cout << upper_bound(all(trie2[cur2].pos),trie1[cur1].pos.back())-lower_bound(all(trie2[cur2].pos),trie1[cur1].pos[0]) << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 507640 KB Output is correct
2 Correct 292 ms 507640 KB Output is correct
3 Correct 299 ms 507512 KB Output is correct
4 Correct 301 ms 507516 KB Output is correct
5 Correct 304 ms 507512 KB Output is correct
6 Correct 297 ms 507756 KB Output is correct
7 Correct 292 ms 507640 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 586616 KB Output is correct
2 Correct 569 ms 582724 KB Output is correct
3 Correct 542 ms 585288 KB Output is correct
4 Correct 530 ms 582136 KB Output is correct
5 Correct 523 ms 588024 KB Output is correct
6 Correct 530 ms 588920 KB Output is correct
7 Correct 412 ms 531456 KB Output is correct
8 Correct 597 ms 572472 KB Output is correct
9 Correct 558 ms 564036 KB Output is correct
10 Correct 510 ms 560760 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 509552 KB Output is correct
2 Correct 325 ms 509368 KB Output is correct
3 Correct 331 ms 509304 KB Output is correct
4 Correct 320 ms 509184 KB Output is correct
5 Correct 332 ms 509304 KB Output is correct
6 Correct 337 ms 509176 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 507640 KB Output is correct
2 Correct 292 ms 507640 KB Output is correct
3 Correct 299 ms 507512 KB Output is correct
4 Correct 301 ms 507516 KB Output is correct
5 Correct 304 ms 507512 KB Output is correct
6 Correct 297 ms 507756 KB Output is correct
7 Correct 292 ms 507640 KB Output is correct
8 Correct 552 ms 586616 KB Output is correct
9 Correct 569 ms 582724 KB Output is correct
10 Correct 542 ms 585288 KB Output is correct
11 Correct 530 ms 582136 KB Output is correct
12 Correct 523 ms 588024 KB Output is correct
13 Correct 530 ms 588920 KB Output is correct
14 Correct 412 ms 531456 KB Output is correct
15 Correct 597 ms 572472 KB Output is correct
16 Correct 558 ms 564036 KB Output is correct
17 Correct 510 ms 560760 KB Output is correct
18 Correct 328 ms 509552 KB Output is correct
19 Correct 325 ms 509368 KB Output is correct
20 Correct 331 ms 509304 KB Output is correct
21 Correct 320 ms 509184 KB Output is correct
22 Correct 332 ms 509304 KB Output is correct
23 Correct 337 ms 509176 KB Output is correct
24 Correct 559 ms 574200 KB Output is correct
25 Correct 566 ms 574840 KB Output is correct
26 Correct 568 ms 573692 KB Output is correct
27 Correct 547 ms 573688 KB Output is correct
28 Correct 550 ms 538708 KB Output is correct
29 Correct 410 ms 520892 KB Output is correct