oj.uz

Submission #290392

# Submission time Handle Problem Language Result Execution time Memory
290392 2020-09-03T17:38:32 Z alexandra_udristoiu Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 537 ms 223896 KB 
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define DIM 100005
using namespace std;
int n, m, k, i, j, u, ii;
int ind[DIM], sol[DIM];
char p[DIM], q[DIM];
vector<char> v[DIM], c[DIM];
struct str{
    int p, u, ind;
};
str w[DIM];
struct trie1{
    int minim, maxim;
    trie1 *f[5];
    trie1(){
        minim = 10000000;
        maxim = 0;
        f[4] = f[1] = f[2] = f[3] = NULL;
    }
};
trie1 *r1;
struct trie2{
    vector<int> v;
    trie2 *f[5];
    trie2(){
        f[4] = f[1] = f[2] = f[3] = NULL;
    }
};
trie2 *r2;
void read(char s[]){
    cin>> s;
    k = strlen(s);
    for(int i = 0; i < k; i++){
        if(s[i] == 'A'){
            s[i] = 1;
        }
        if(s[i] == 'C'){
            s[i] = 2;
        }
        if(s[i] == 'G'){
            s[i] = 3;
        }
        if(s[i] == 'U'){
            s[i] = 4;
        }
    }
}
int cmp2(str a, str b){
    return a.p > b.p;
}
int cmp(int a, int b){
    for(int i = 0; i < min(v[a].size(), v[b].size() ); i++){
        if(v[a][i] != v[b][i]){
            return v[a][i] < v[b][i];
        }
    }
    return v[a].size() < v[b].size();
}
void adauga1(trie1 *r, char *s, int ind){
    r->minim = min(r->minim, ind);
    r->maxim = max(r->maxim, ind);
    if(*s != 0){
        if(r->f[*s] == NULL){
            r->f[*s] = new trie1;
        }
        adauga1(r->f[*s], s + 1, ind);
    }
}
void query1(trie1 *r, char *s, str &w){
    if(*s == 0){
        w.p = r->minim;
        w.u = r->maxim;
    }
    else{
        if(r->f[*s] != NULL){
            query1(r->f[*s], s + 1, w);
        }
    }
}
void adauga2(trie2 *r, char *s, int ind){
    r->v.push_back(ind);
    if(*s != 0){
        if(r->f[*s] == NULL){
            r->f[*s] = new trie2;
        }
        adauga2(r->f[*s], s + 1, ind);
    }
}
int query2(trie2 *r, char *s, int ind){
    if(*s == 0){
        int st, dr, mid;
        st = 0;
        dr = r->v.size() - 1;
        while(st <= dr){
            mid = (st + dr) / 2;
            if(r->v[mid] <= ind){
                dr = mid - 1;
            }
            else{
                st = mid + 1;
            }
        }
        return r->v.size() - st;
    }
    if(r->f[*s] == NULL){
        return 0;
    }
    return query2(r->f[*s], s + 1, ind);
}
void copiere(vector<char> v){
    for(int i = 0; i < v.size(); i++){
        p[i] = v[i];
    }
    p[ v.size() ] = 0;
}
int main(){
    r1 = new trie1;
    r2 = new trie2;
    cin>> n >> m;
    for(i = 1; i <= n; i++){
        read(p);
        ind[i] = i;
        for(j = 0; j < k; j++){
            v[i].push_back(p[j]);
        }
    }
    sort(ind + 1, ind + n + 1, cmp);
    for(i = 1; i <= n; i++){
        copiere(v[ ind[i] ]);
        adauga1(r1, p, i);
    }
    for(i = 1; i <= m; i++){
        read(p);
        w[i].ind = i;
        w[i].p = 1000000;
        query1(r1, p, w[i]);
        read(q);
        for(j = 0; j < k; j++){
            c[i].push_back(q[j]);
        }
    }
    sort(w + 1, w + m + 1, cmp2);
    u = 1;
    for(ii = 1; ii <= n; ii++){
        for(i = 0, j = v[ii].size() - 1; i < j; i++, j--){
            swap(v[ii][i], v[ii][j]);
        }
    }
    for(ii = 1; ii <= m; ii++){
        for(i = 0, j = c[ii].size() - 1; i < j; i++, j--){
            swap(c[ii][i], c[ii][j]);
        }
    }
    while(w[u].p > n){
        u++;
    }
    for(i = n; i >= 1; i--){
        copiere(v[ ind[i] ]);
        adauga2(r2, p, i);
        while(w[u].p == i){
            copiere(c[ w[u].ind ]);
            sol[ w[u].ind ] = query2(r2, p, w[u].u);
            u++;
        }
    }
    for(i = 1; i <= m; i++){
        cout<< sol[i] <<"\n";
    }
}

Compilation message

selling_rna.cpp: In function 'int cmp(int, int)':
selling_rna.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   55 |     for(int i = 0; i < min(v[a].size(), v[b].size() ); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void adauga1(trie1*, char*, int)':
selling_rna.cpp:66:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   66 |         if(r->f[*s] == NULL){
      |                 ^~
selling_rna.cpp:67:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   67 |             r->f[*s] = new trie1;
      |                  ^~
selling_rna.cpp:69:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   69 |         adauga1(r->f[*s], s + 1, ind);
      |                      ^~
selling_rna.cpp: In function 'void query1(trie1*, char*, str&)':
selling_rna.cpp:78:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   78 |         if(r->f[*s] != NULL){
      |                 ^~
selling_rna.cpp:79:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   79 |             query1(r->f[*s], s + 1, w);
      |                         ^~
selling_rna.cpp: In function 'void adauga2(trie2*, char*, int)':
selling_rna.cpp:86:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   86 |         if(r->f[*s] == NULL){
      |                 ^~
selling_rna.cpp:87:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |             r->f[*s] = new trie2;
      |                  ^~
selling_rna.cpp:89:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |         adauga2(r->f[*s], s + 1, ind);
      |                      ^~
selling_rna.cpp: In function 'int query2(trie2*, char*, int)':
selling_rna.cpp:108:13: warning: array subscript has type 'char' [-Wchar-subscripts]
  108 |     if(r->f[*s] == NULL){
      |             ^~
selling_rna.cpp:111:24: warning: array subscript has type 'char' [-Wchar-subscripts]
  111 |     return query2(r->f[*s], s + 1, ind);
      |                        ^~
selling_rna.cpp: In function 'void copiere(std::vector<char>)':
selling_rna.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 223896 KB Output is correct
2 Correct 489 ms 216444 KB Output is correct
3 Correct 419 ms 147832 KB Output is correct
4 Correct 418 ms 141940 KB Output is correct
5 Correct 401 ms 219840 KB Output is correct
6 Correct 411 ms 223096 KB Output is correct
7 Correct 353 ms 24496 KB Output is correct
8 Correct 534 ms 145020 KB Output is correct
9 Correct 507 ms 124792 KB Output is correct
10 Correct 362 ms 117880 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 10160 KB Output is correct
2 Correct 66 ms 9080 KB Output is correct
3 Correct 78 ms 9848 KB Output is correct
4 Correct 71 ms 9076 KB Output is correct
5 Correct 67 ms 8952 KB Output is correct
6 Correct 81 ms 9844 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct
8 Correct 479 ms 223896 KB Output is correct
9 Correct 489 ms 216444 KB Output is correct
10 Correct 419 ms 147832 KB Output is correct
11 Correct 418 ms 141940 KB Output is correct
12 Correct 401 ms 219840 KB Output is correct
13 Correct 411 ms 223096 KB Output is correct
14 Correct 353 ms 24496 KB Output is correct
15 Correct 534 ms 145020 KB Output is correct
16 Correct 507 ms 124792 KB Output is correct
17 Correct 362 ms 117880 KB Output is correct
18 Correct 91 ms 10160 KB Output is correct
19 Correct 66 ms 9080 KB Output is correct
20 Correct 78 ms 9848 KB Output is correct
21 Correct 71 ms 9076 KB Output is correct
22 Correct 67 ms 8952 KB Output is correct
23 Correct 81 ms 9844 KB Output is correct
24 Correct 505 ms 189288 KB Output is correct
25 Correct 526 ms 190948 KB Output is correct
26 Correct 482 ms 186876 KB Output is correct
27 Correct 427 ms 125560 KB Output is correct
28 Correct 537 ms 51440 KB Output is correct
29 Correct 406 ms 22240 KB Output is correct