Submission #343319

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343319	2021-01-03T16:25:20 Z	AmirrezaM	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	320 ms	165996 KB

selling_rna

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppiii;

// vectors and Sets:
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define it iterator
#define SZ(x) (ll)((x).size())
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rend(), (c).rbegin

// pairs
#define mp make_pair
#define fr first
#define sc second

// loops
#define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
#define ROF(i , n , m) for(int (i) = (n) ; (i) >= (m) ; (i)--)
//#define FOR(n) for(int (i) = (o) ; (i) < (n) ; (i)++)
//#define ROF(n) for(int (i) = (m) ; (i) >= (0) ; (i)--)

// useful numbers
#define mod (1e9 + 7)
#define INF ((1 << 64) - 1)
#define BPT(n) pow(2,floor(log2((n))));
#define LPT(n) pow(2,ceil(log2((n))*1.0));

// execution time check and Debug
#define StartEX; clock_t startExeTime = clock();
#define EndEX; clock_t endExeTime = clock();
#define ExTime; cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
#define debug(x) cerr << #x << " : " << x << '\n'
#define endl "\n"

// time optimization
#define Heh ios::sync_with_stdio(false);cin.tie(0);
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O0")
#pragma GCC optimize("O1")

//Calculates b'th power of a
ll pw(int a,int b){
    ll ret = 1;
    ll mul = a;
    while(b > 0){
        if(b&1)
            ret *= mul;
        mul *= mul;
        b /= 2;
    }
    return ret;
}

//Converts s string to int
ll to_int(string s){
    ll ret = 0;
    FOR(i,0,s.size()){
        ret += pw(10,s.size()-i-1) * (ll)(s[i] - '0');
    }
    return ret;
}
int sz1 = 3, sz2 = 3;
const int MAXS = 2e6 + 100;
const int MAXN = 2e5 + 100;
int child1[MAXS][4];
int child2[MAXS][4];
int mn[MAXS] , mx[MAXS];
vc<int> ind[MAXS];
int inv[MAXN];
string s[MAXN];
void insert1(int idx , int v , int l){
    mn[v] = min(mn[v] , inv[idx]);
    mx[v] = max(mx[v] , inv[idx]);
    if(l < s[idx].size() - 1){
        if(!child1[v][s[idx][l+1]-'0']) child1[v][s[idx][l+1]-'0'] = ++sz1;
        insert1(idx , child1[v][s[idx][l+1]-'0'] , l + 1);
    }
}
void insert2(int idx , int v , int l){
    ind[v].pb(inv[idx]);
    if(l){
        if(!child2[v][s[idx][l-1]-'0']) child2[v][s[idx][l-1]-'0'] = ++sz2;
        insert2(idx , child2[v][s[idx][l-1]-'0'] , l-1);
    }
}
int search1(string& s , int node , int l){
    if(mx[node] == -1e9) return -1;
    if(l == s.size()-1) return node;
    if(child1[node][s[l+1]-'0'] == 0) return -1;
    return search1(s , child1[node][s[l+1]-'0'] , l+1);
}
int search2(string& s , int node , int l){
    if(ind[node].size() == 0) return -1;
    if(l == 0) return node;
    if(child2[node][s[l-1]-'0'] == 0) return -1;
    return search2(s , child2[node][s[l-1]-'0'] , l-1);
}
int main()
{
    Heh;
    FOR(i,0,MAXS) mn[i] = 1e9 , mx[i] = -1e9;
    int n , m;
    cin >> n >> m;
    pair<string,int> tmp[n];
    FOR(i,0,n){
        cin >> s[i];
        FOR(j,0,s[i].size()){
            if(s[i][j] == 'A') s[i][j] = '0';
            if(s[i][j] == 'C') s[i][j] = '1';
            if(s[i][j] == 'G') s[i][j] = '2';
            if(s[i][j] == 'U') s[i][j] = '3';
        }
        tmp[i].fr = s[i] , tmp[i].sc = i;
    }
    sort(tmp , tmp+n);
    FOR(i,0,n) inv[tmp[i].sc] = i , insert1(tmp[i].sc , tmp[i].fr[0] - '0' , 0) ,insert2(tmp[i].sc , tmp[i].fr[tmp[i].fr.size()-1] - '0' , tmp[i].fr.size() - 1);
    while(m--){
        string p , q;
        cin >> p >> q;
        FOR(j,0,p.size()){
            if(p[j] == 'A') p[j] = '0';
            if(p[j] == 'C') p[j] = '1';
            if(p[j] == 'G') p[j] = '2';
            if(p[j] == 'U') p[j] = '3';
        }
        FOR(j,0,q.size()){
            if(q[j] == 'A') q[j] = '0';
            if(q[j] == 'C') q[j] = '1';
            if(q[j] == 'G') q[j] = '2';
            if(q[j] == 'U') q[j] = '3';
        }
        int tmp = search1(p , p[0] - '0' , 0);
        if(tmp == -1){
            cout << 0 << endl;
            continue;
        }
        int l = mn[tmp] , r = mx[tmp];
        tmp = search2(q , q[q.size()-1] - '0' , q.size()-1);
        if(tmp == -1){
            cout << 0 << endl;
            continue;
        }
        int ans = upper_bound(all(ind[tmp]) , r) - lower_bound(all(ind[tmp]) , l);
        cout << ans << endl;
    }
    // Doesn't Ac? Read the Bottom :/
}

// stuff you should look for(Thanks Benq)
//	*** int overflow, array bounds
//	* special cases (n=1?)
//	**** do smth instead of nothing and stay organized
//	* WRITE STUFF DOWN
//	*** DON'T GET STUCK ON ONE APPROACH

Compilation message

selling_rna.cpp:38:9: warning: ISO C++11 requires whitespace after the macro name
   38 | #define StartEX; clock_t startExeTime = clock();
      |         ^~~~~~~
selling_rna.cpp:39:9: warning: ISO C++11 requires whitespace after the macro name
   39 | #define EndEX; clock_t endExeTime = clock();
      |         ^~~~~
selling_rna.cpp:40:9: warning: ISO C++11 requires whitespace after the macro name
   40 | #define ExTime; cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
      |         ^~~~~~
selling_rna.cpp: In function 'll to_int(std::string)':
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:67:5: note: in expansion of macro 'FOR'
   67 |     FOR(i,0,s.size()){
      |     ^~~
selling_rna.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
selling_rna.cpp:67:5: note: in expansion of macro 'FOR'
   67 |     FOR(i,0,s.size()){
      |     ^~~
selling_rna.cpp: In function 'void insert1(int, int, int)':
selling_rna.cpp:84:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     if(l < s[idx].size() - 1){
      |        ~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int search1(std::string&, int, int)':
selling_rna.cpp:98:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     if(l == s.size()-1) return node;
      |        ~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:111:5: note: in expansion of macro 'FOR'
  111 |     FOR(i,0,MAXS) mn[i] = 1e9 , mx[i] = -1e9;
      |     ^~~
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:115:5: note: in expansion of macro 'FOR'
  115 |     FOR(i,0,n){
      |     ^~~
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:117:9: note: in expansion of macro 'FOR'
  117 |         FOR(j,0,s[i].size()){
      |         ^~~
selling_rna.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
selling_rna.cpp:117:9: note: in expansion of macro 'FOR'
  117 |         FOR(j,0,s[i].size()){
      |         ^~~
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:126:5: note: in expansion of macro 'FOR'
  126 |     FOR(i,0,n) inv[tmp[i].sc] = i , insert1(tmp[i].sc , tmp[i].fr[0] - '0' , 0) ,insert2(tmp[i].sc , tmp[i].fr[tmp[i].fr.size()-1] - '0' , tmp[i].fr.size() - 1);
      |     ^~~
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:130:9: note: in expansion of macro 'FOR'
  130 |         FOR(j,0,p.size()){
      |         ^~~
selling_rna.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
selling_rna.cpp:130:9: note: in expansion of macro 'FOR'
  130 |         FOR(j,0,p.size()){
      |         ^~~
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:136:9: note: in expansion of macro 'FOR'
  136 |         FOR(j,0,q.size()){
      |         ^~~
selling_rna.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
selling_rna.cpp:136:9: note: in expansion of macro 'FOR'
  136 |         FOR(j,0,q.size()){
      |         ^~~

Subtask #1

10.0 / 10.0

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

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	278 ms	165996 KB	Output is correct
2	Correct	280 ms	161180 KB	Output is correct
3	Correct	199 ms	115436 KB	Output is correct
4	Correct	198 ms	113644 KB	Output is correct
5	Correct	243 ms	148460 KB	Output is correct
6	Correct	247 ms	149604 KB	Output is correct
7	Correct	143 ms	81040 KB	Output is correct
8	Correct	280 ms	124396 KB	Output is correct
9	Correct	252 ms	116716 KB	Output is correct
10	Correct	204 ms	115564 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	72428 KB	Output is correct
2	Correct	85 ms	71404 KB	Output is correct
3	Correct	91 ms	72044 KB	Output is correct
4	Correct	72 ms	71532 KB	Output is correct
5	Correct	77 ms	71532 KB	Output is correct
6	Correct	85 ms	71916 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	69228 KB	Output is correct
2	Correct	43 ms	69228 KB	Output is correct
3	Correct	43 ms	69228 KB	Output is correct
4	Correct	44 ms	69228 KB	Output is correct
5	Correct	43 ms	69228 KB	Output is correct
6	Correct	44 ms	69356 KB	Output is correct
7	Correct	43 ms	69228 KB	Output is correct
8	Correct	278 ms	165996 KB	Output is correct
9	Correct	280 ms	161180 KB	Output is correct
10	Correct	199 ms	115436 KB	Output is correct
11	Correct	198 ms	113644 KB	Output is correct
12	Correct	243 ms	148460 KB	Output is correct
13	Correct	247 ms	149604 KB	Output is correct
14	Correct	143 ms	81040 KB	Output is correct
15	Correct	280 ms	124396 KB	Output is correct
16	Correct	252 ms	116716 KB	Output is correct
17	Correct	204 ms	115564 KB	Output is correct
18	Correct	89 ms	72428 KB	Output is correct
19	Correct	85 ms	71404 KB	Output is correct
20	Correct	91 ms	72044 KB	Output is correct
21	Correct	72 ms	71532 KB	Output is correct
22	Correct	77 ms	71532 KB	Output is correct
23	Correct	85 ms	71916 KB	Output is correct
24	Correct	296 ms	149996 KB	Output is correct
25	Correct	320 ms	149996 KB	Output is correct
26	Correct	282 ms	149100 KB	Output is correct
27	Correct	201 ms	109548 KB	Output is correct
28	Correct	311 ms	97644 KB	Output is correct
29	Correct	196 ms	79200 KB	Output is correct