oj.uz

Submission #1025110

# Submission time Handle Problem Language Result Execution time Memory
1025110 2024-07-16T16:05:52 Z _8_8_ Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 641876 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 3e5 + 20, MOD = (int)1e9+7;

struct node{
    node *next[26];
    int tin,tout;
    vector<int> id;
    node(){
        tin = 0,tout = 0;
        for(int i = 0;i < 26;i++){
            next[i] = nullptr;
        }
    }
};
 
node *p = new node(),*s = new node();
using pnode = node *;
int sp = 0,ss = 0;
int n,q;
void add(pnode v,string &x,int j){
    for(int i = 0;i < (int)x.size();i++){
        if(!v->next[(x[i] - 'A')]){
            v->next[(x[i] - 'A')] = new node();
        }
        v = v->next[(x[i] - 'A')];
    }
    v->id.push_back(j);
}
int timer = 0;
array<int,2> pt[N];
vector<int> c,c1;
void dfs(pnode v){
    v->tin = ++timer;
    for(int k:v->id){
        if(pt[k][0] == -1){
            pt[k][0] = timer;
            c.push_back(timer);
        }else{
            pt[k][1] = timer;
            c1.push_back(timer);
        }
    }
    for(int t = 0;t < 26;t++){
        if(v->next[t]){
            dfs(v->next[t]);
        }
    }
    v->tout = ++timer;
}
pair<int,int> get_tin(pnode v,string &x){
    for(int i = 0;i < (int)x.size();i++){
        if(v->next[(x[i] - 'A')]){
            v = v->next[(x[i] - 'A')];
        }else return {-1,-1};
    }
    return {v->tin,v->tout};
}
void make(vector<int> &x){
    sort(x.begin(),x.end());
    x.resize(unique(x.begin(),x.end()) - x.begin());
}
string X[N],Y[N];
int find(vector<int> &x,int a){
    int it = lower_bound(x.begin(),x.end(),a) - x.begin();
    return it + 1;
}
void test(){
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        string t;
        cin >> t;
        add(p,t,i);
        reverse(t.begin(),t.end());
        add(s,t,i);
        pt[i] = {-1,-1};
    }
    dfs(p);
    timer = 0;
    dfs(s);
    for(int i = 0;i < q;i++){
        string x,y;
        cin >> x >> y;
        reverse(y.begin(),y.end());
        X[i] = x;
        Y[i] = y;
        pair<int,int> ti = get_tin(p,x),to = get_tin(s,y);
        c.push_back(ti.first);
        c.push_back(ti.second);
        c1.push_back(to.first);
        c1.push_back(to.second);
    }
    make(c);
    make(c1);
    for(int i = 1;i <= n;i++){
        pt[i][0] = find(c,pt[i][0]);
        pt[i][1] = find(c1,pt[i][1]);
    }
    for(int i = 0;i < q;i++){
        pair<int,int> ti = get_tin(p,X[i]),to = get_tin(s,Y[i]);
        ti.first = find(c,ti.first);
        ti.second = find(c,ti.second);
        to.first = find(c1,to.first);
        to.second = find(c1,to.second);
        int res = 0;
        for(int j = 1;j <= n;j++){
            if(pt[j][0] >= ti.first && pt[j][0] <= ti.second && pt[j][1] >=to.first && pt[j][1] <= to.second){
                res++;
            }
        }
        cout << res << '\n';

    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--){
        test();
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19292 KB Output is correct
2 Correct 8 ms 19260 KB Output is correct
3 Correct 8 ms 19292 KB Output is correct
4 Correct 8 ms 19292 KB Output is correct
5 Correct 9 ms 19288 KB Output is correct
6 Correct 9 ms 19292 KB Output is correct
7 Correct 10 ms 19292 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 519252 KB Output is correct
2 Correct 460 ms 492776 KB Output is correct
3 Correct 421 ms 512160 KB Output is correct
4 Correct 448 ms 488528 KB Output is correct
5 Correct 701 ms 632912 KB Output is correct
6 Correct 706 ms 641876 KB Output is correct
7 Correct 90 ms 29840 KB Output is correct
8 Correct 465 ms 387008 KB Output is correct
9 Correct 403 ms 329044 KB Output is correct
10 Correct 278 ms 315316 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1531 ms 22156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19292 KB Output is correct
2 Correct 8 ms 19260 KB Output is correct
3 Correct 8 ms 19292 KB Output is correct
4 Correct 8 ms 19292 KB Output is correct
5 Correct 9 ms 19288 KB Output is correct
6 Correct 9 ms 19292 KB Output is correct
7 Correct 10 ms 19292 KB Output is correct
8 Correct 414 ms 519252 KB Output is correct
9 Correct 460 ms 492776 KB Output is correct
10 Correct 421 ms 512160 KB Output is correct
11 Correct 448 ms 488528 KB Output is correct
12 Correct 701 ms 632912 KB Output is correct
13 Correct 706 ms 641876 KB Output is correct
14 Correct 90 ms 29840 KB Output is correct
15 Correct 465 ms 387008 KB Output is correct
16 Correct 403 ms 329044 KB Output is correct
17 Correct 278 ms 315316 KB Output is correct
18 Execution timed out 1531 ms 22156 KB Time limit exceeded
19 Halted 0 ms 0 KB -