oj.uz

Submission #933300

# Submission time Handle Problem Language Result Execution time Memory
933300 2024-02-25T12:04:06 Z parlimoos Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 491 ms 1009476 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

struct nodel{
    nodel *ch[4] = {NULL , NULL , NULL , NULL};
    int time[2];
};
struct noder{
    noder *ch[4] = {NULL , NULL , NULL , NULL};
    vector<int> tms;
};

int n , m;
vector<string> a;
vector<string> ls , rs;
nodel tirel[10000001];
noder tirer[10000001];
int cntl = 0 , cntr = 0;
nodel *ais[100000];

int ch2int(char &e){
    if(e == 'A') return 0;
    if(e == 'U') return 1;
    if(e == 'G') return 2;
    return 3;
}
void addTirel(int inx){
    nodel *cur = &tirel[0];
    for(int i = 0 ; i < (int)a[inx].size() ; i++){
        int d = ch2int(a[inx][i]);
        if((cur -> ch)[d] == NULL) (cur -> ch)[d] = &tirel[++cntl];
        cur = (cur -> ch)[d];
    }
    ais[inx] = cur;
}
int timer = -1;
void dfsTirel(nodel *cur = &tirel[0]){
    (cur -> time)[0] = ++timer;
    for(int u = 0 ; u < 4 ; u++) if((cur -> ch)[u] != NULL) dfsTirel((cur -> ch)[u]);
    (cur -> time)[1] = timer;
}
void addTirer(int inx){
    noder *cur = &tirer[0];
    for(int i = (int)a[inx].size() - 1 ; i >= 0 ; i--){
        int d = ch2int(a[inx][i]);
        if((cur -> ch)[d] == NULL) (cur -> ch)[d] = &tirer[++cntr];
        cur = (cur -> ch)[d];
        (cur -> tms).pb((ais[inx] -> time)[0]);
    }
}
void drawTirer(){
    for(int i = 0 ; i <= cntr ; i++) sort((tirer[i].tms).bg() , (tirer[i].tms).end());
}
nodel *getTirel(int inx){
    nodel *cur = &tirel[0];
    for(int i = 0 ; i < (int)ls[inx].size() ; i++){
        int d = ch2int(ls[inx][i]);
        if((cur -> ch)[d] == NULL) return NULL;
        cur = (cur -> ch)[d];
    }
    return cur;
}
noder *getTirer(int inx){
    noder *cur = &tirer[0];
    for(int i = (int)rs[inx].size() - 1 ; i >= 0 ; i--){
        int d = ch2int(rs[inx][i]);
        if((cur -> ch)[d] == NULL) return NULL;
        cur = (cur -> ch)[d];
    }
    return cur;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0 ; i < n ; i++){
        string d;
        cin >> d;
        a.pb(d);
    }
    for(int i = 0 ; i < m ; i++){
        string l , r;
        cin >> l >> r;
        ls.pb(l) , rs.pb(r);
    }
    for(int i = 0 ; i < n ; i++) addTirel(i);
    dfsTirel();
    for(int i = 0 ; i < n ; i++) addTirer(i);
    drawTirer();
    for(int i = 0 ; i < m ; i++){
        auto itr1 = getTirel(i);
        auto itr2 = getTirer(i);
        if(itr1 == NULL or itr2 == NULL){
            cout << "0\n";
            continue;
        }
        int l = (itr1 -> time)[0] , r = (itr1 -> time)[1];
        int o = int(ub((itr2 -> tms).bg() , (itr2 -> tms).end() , r) - lb((itr2 -> tms).bg() , (itr2 -> tms).end() , l));
        cout << o << endl;
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 939800 KB Output is correct
2 Correct 446 ms 939916 KB Output is correct
3 Correct 334 ms 939800 KB Output is correct
4 Correct 340 ms 939600 KB Output is correct
5 Correct 332 ms 939604 KB Output is correct
6 Correct 336 ms 939904 KB Output is correct
7 Correct 333 ms 939580 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 1009476 KB Output is correct
2 Correct 448 ms 1006544 KB Output is correct
3 Correct 475 ms 959948 KB Output is correct
4 Correct 484 ms 959908 KB Output is correct
5 Correct 448 ms 983504 KB Output is correct
6 Correct 450 ms 984484 KB Output is correct
7 Correct 408 ms 959640 KB Output is correct
8 Correct 471 ms 980384 KB Output is correct
9 Correct 468 ms 976772 KB Output is correct
10 Correct 442 ms 971016 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 947404 KB Output is correct
2 Correct 365 ms 944020 KB Output is correct
3 Correct 364 ms 946552 KB Output is correct
4 Correct 348 ms 946120 KB Output is correct
5 Correct 355 ms 943848 KB Output is correct
6 Correct 351 ms 946376 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 939800 KB Output is correct
2 Correct 446 ms 939916 KB Output is correct
3 Correct 334 ms 939800 KB Output is correct
4 Correct 340 ms 939600 KB Output is correct
5 Correct 332 ms 939604 KB Output is correct
6 Correct 336 ms 939904 KB Output is correct
7 Correct 333 ms 939580 KB Output is correct
8 Correct 467 ms 1009476 KB Output is correct
9 Correct 448 ms 1006544 KB Output is correct
10 Correct 475 ms 959948 KB Output is correct
11 Correct 484 ms 959908 KB Output is correct
12 Correct 448 ms 983504 KB Output is correct
13 Correct 450 ms 984484 KB Output is correct
14 Correct 408 ms 959640 KB Output is correct
15 Correct 471 ms 980384 KB Output is correct
16 Correct 468 ms 976772 KB Output is correct
17 Correct 442 ms 971016 KB Output is correct
18 Correct 352 ms 947404 KB Output is correct
19 Correct 365 ms 944020 KB Output is correct
20 Correct 364 ms 946552 KB Output is correct
21 Correct 348 ms 946120 KB Output is correct
22 Correct 355 ms 943848 KB Output is correct
23 Correct 351 ms 946376 KB Output is correct
24 Correct 476 ms 1000132 KB Output is correct
25 Correct 483 ms 1002644 KB Output is correct
26 Correct 461 ms 998912 KB Output is correct
27 Correct 485 ms 961400 KB Output is correct
28 Correct 491 ms 974740 KB Output is correct
29 Correct 396 ms 958536 KB Output is correct