oj.uz

답안 #343319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343319 2021-01-03T16:25:20 Z AmirrezaM Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 320 ms 165996 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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