oj.uz

Submission #1016900

# Submission time Handle Problem Language Result Execution time Memory
1016900 2024-07-08T14:56:27 Z ByeWorld Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 213 ms 138928 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e5+10;
const int MAXA = 110;
const int INF = 1e18+10;
const int LOG = 19;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
void chmx(int &a, int b){ a = max(a, b); }

int n, k, ans[MAXN];
string p[MAXN], q[MAXN];
vector <pair<string,int>> vec;
string te;

struct seg {
    int cnt, idx;
    seg* a[4];
    void bd(int nw){
        if(a[nw] == NULL){
            a[nw] = new seg(); a[nw]->idx = idx+1; a[nw]->cnt = 0;
        }
    }
    void upd(){
        // if(idx!=-1) cout << te[idx] << ' '<< te << " te\n";
        cnt++;
        // cout << idx << ' ' << te <<"pp\n";
        if(idx+1==te.size()) return;
        if(te[idx+1] == 'A'){
            bd(0); a[0]->upd();
        } else if(te[idx+1] == 'C'){
            bd(1); a[1]->upd();
        } else if(te[idx+1] == 'U'){
            bd(2); a[2]->upd();
        } else if(te[idx+1] == 'G'){
            bd(3); a[3]->upd();
        }
    }
    int que(){
        if(idx+1==te.size()) return cnt;
        if(te[idx+1] == 'A'){
            bd(0); return a[0]->que();
        } else if(te[idx+1] == 'C'){
            bd(1); return a[1]->que();
        } else if(te[idx+1] == 'U'){
            bd(2); return a[2]->que();
        } else if(te[idx+1] == 'G'){
            bd(3); return a[3]->que();
        }
        assert(false);
    }
} *A;

signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    A = new seg(); A->idx = -1;
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        string s; cin >> s; vec.pb({s, 0});
    }
    for(int i=1; i<=k; i++){
        cin >> p[i] >> q[i];
        for(int j=0; j<q[i].size()/2; j++) swap(q[i][j], q[i][q[i].size()-j-1]);

        vec.pb({p[i], -i});
        string te = p[i]; te += 'Z';
        vec.pb({te, i});
    }
    sort(vec.begin(), vec.end());
    // for(auto in : vec) cout << in.fi << ' ' << in.se << " vec\n";

    for(auto in : vec){
        if(in.se==0){
            te = in.fi;
            for(int i=0; i<te.size()/2; i++) swap(te[i], te[(int)te.size()-i-1]);
                // cout << te << " te\n";
            A->upd();
        // cout << A->a[1]->cnt << " cnt\n";
        } else if(in.se < 0){
            int id = -in.se, idx = 0;
            te = q[id];
            int ret = A->que();
            ans[id] -= ret;
            // cout << ret << ' ' << id << "id min\n";

        } else {
            int id = in.se, idx = 0;
            te = q[id];
            int ret = A->que();
            ans[id] += ret;
            // cout << ret << ' ' << id << "id plus\n";
        }
    }
    for(int i=1; i<=k; i++) cout << ans[i] << '\n';
}

Compilation message

selling_rna.cpp: In member function 'void seg::upd()':
selling_rna.cpp:44:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if(idx+1==te.size()) return;
      |            ~~~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'long long int seg::que()':
selling_rna.cpp:56:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if(idx+1==te.size()) return cnt;
      |            ~~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:79:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int j=0; j<q[i].size()/2; j++) swap(q[i][j], q[i][q[i].size()-j-1]);
      |                      ~^~~~~~~~~~~~~~
selling_rna.cpp:91:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             for(int i=0; i<te.size()/2; i++) swap(te[i], te[(int)te.size()-i-1]);
      |                          ~^~~~~~~~~~~~
selling_rna.cpp:96:30: warning: unused variable 'idx' [-Wunused-variable]
   96 |             int id = -in.se, idx = 0;
      |                              ^~~
selling_rna.cpp:103:29: warning: unused variable 'idx' [-Wunused-variable]
  103 |             int id = in.se, idx = 0;
      |                             ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 138928 KB Output is correct
2 Correct 150 ms 136552 KB Output is correct
3 Correct 75 ms 16488 KB Output is correct
4 Correct 76 ms 16512 KB Output is correct
5 Correct 109 ms 90472 KB Output is correct
6 Correct 112 ms 91500 KB Output is correct
7 Correct 97 ms 24000 KB Output is correct
8 Correct 137 ms 68716 KB Output is correct
9 Correct 130 ms 61944 KB Output is correct
10 Correct 92 ms 52588 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 18884 KB Output is correct
2 Correct 40 ms 14284 KB Output is correct
3 Correct 45 ms 12232 KB Output is correct
4 Correct 37 ms 13768 KB Output is correct
5 Correct 37 ms 14056 KB Output is correct
6 Correct 46 ms 13260 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 148 ms 138928 KB Output is correct
9 Correct 150 ms 136552 KB Output is correct
10 Correct 75 ms 16488 KB Output is correct
11 Correct 76 ms 16512 KB Output is correct
12 Correct 109 ms 90472 KB Output is correct
13 Correct 112 ms 91500 KB Output is correct
14 Correct 97 ms 24000 KB Output is correct
15 Correct 137 ms 68716 KB Output is correct
16 Correct 130 ms 61944 KB Output is correct
17 Correct 92 ms 52588 KB Output is correct
18 Correct 51 ms 18884 KB Output is correct
19 Correct 40 ms 14284 KB Output is correct
20 Correct 45 ms 12232 KB Output is correct
21 Correct 37 ms 13768 KB Output is correct
22 Correct 37 ms 14056 KB Output is correct
23 Correct 46 ms 13260 KB Output is correct
24 Correct 155 ms 122588 KB Output is correct
25 Correct 190 ms 126676 KB Output is correct
26 Correct 145 ms 120292 KB Output is correct
27 Correct 94 ms 18508 KB Output is correct
28 Correct 213 ms 48068 KB Output is correct
29 Correct 154 ms 30640 KB Output is correct