oj.uz

Submission #445831

# Submission time Handle Problem Language Result Execution time Memory
445831 2021-07-19T19:41:09 Z JovanB Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 546 ms 604448 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 100000;

int x[N+5];
int y[N+5];

const int MAXC = 4000000;
int gde[MAXC+5][4];

int tjm;

vector <pair <int, int>> graf[MAXC+5];
vector <int> koji[MAXC+5];
vector <int> queries[MAXC+5];

void trie_add(int t, int ind, const string &s){
    int v = 0;
    for(int i=0; i<s.size(); i++){
        int x = s[i] - 'A';
        if(!gde[v][x]){
            gde[v][x] = ++tjm;
            graf[v].push_back({tjm, x});
        }
        v = gde[v][x];
    }
    if(t == 1) koji[v].push_back(ind);
    else queries[v].push_back(ind);
}

int xl[N+5], yl[N+5], xr[N+5], yr[N+5];

void dfs(int t, int v){
    int in = ++tjm;
    for(auto c : koji[v]){
        if(t == 1) x[c] = in;
        else y[c] = in;
    }
    for(auto c : graf[v]) dfs(t, c.first);
    int out = tjm;
    for(auto c : queries[v]){
        if(t == 1){
            xl[c] = in, xr[c] = out;
        }
        else{
            yl[c] = in, yr[c] = out;
        }
    }
    queries[v].clear();
    koji[v].clear();
    for(auto c : graf[v]){
        gde[v][c.second] = 0;
    }
    graf[v].clear();
}

string s[N+5];
string qpref[N+5];
string qsuf[N+5];

int bit[MAXC+5];

void bit_add(int x){
    while(x <= MAXC){
        bit[x]++;
        x += x & -x;
    }
}

int bit_get(int x){
    int res = 0;
    while(x){
        res += bit[x];
        x -= x & -x;
    }
    return res;
}

const int INF = 1000000000;

vector <int> upds[MAXC+5];
vector <pair <pair <int, int>, int>> quers[MAXC+5];

int res[N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> s[i];
        for(auto &c : s[i]){
            if(c == 'G') c = 'B';
            if(c == 'U') c = 'D';
        }
        trie_add(1, i, s[i]);
    }
    for(int i=1; i<=m; i++){
        cin >> qpref[i] >> qsuf[i];
        for(auto &c : qpref[i]){
            if(c == 'G') c = 'B';
            if(c == 'U') c = 'D';
        }
        for(auto &c : qsuf[i]){
            if(c == 'G') c = 'B';
            if(c == 'U') c = 'D';
        }
        trie_add(2, i, qpref[i]);
    }
    dfs(1, 0);
    for(int i=1; i<=n; i++){
        reverse(s[i].begin(), s[i].end());
        trie_add(1, i, s[i]);
    }
    for(int i=1; i<=m; i++){
        reverse(qsuf[i].begin(), qsuf[i].end());
        trie_add(2, i, qsuf[i]);
    }
    tjm = 0;
    dfs(2, 0);
    for(int i=1; i<=n; i++){
        upds[y[i]].push_back(x[i]);
    }
    for(int i=1; i<=m; i++){
        quers[yr[i]].push_back({{xl[i], xr[i]}, i});
        quers[yl[i] - 1].push_back({{xl[i], xr[i]}, -i});
    }
    for(int i=1; i<=MAXC; i++){
        for(auto c : upds[i]) bit_add(c);
        for(auto c : quers[i]){
            int ind = c.second;
            int kf = 1;
            if(ind < 0){
                ind = -ind;
                kf = -1;
            }
            res[ind] += kf*(bit_get(c.first.second) - bit_get(c.first.first - 1));
        }
    }
    for(int i=1; i<=m; i++) cout << res[i] << "\n";
    return 0;
}

Compilation message

selling_rna.cpp: In function 'void trie_add(int, int, const string&)':
selling_rna.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 479432 KB Output is correct
2 Correct 278 ms 479476 KB Output is correct
3 Correct 272 ms 479428 KB Output is correct
4 Correct 266 ms 479424 KB Output is correct
5 Correct 269 ms 479388 KB Output is correct
6 Correct 272 ms 479432 KB Output is correct
7 Correct 269 ms 479556 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 576904 KB Output is correct
2 Correct 493 ms 575848 KB Output is correct
3 Correct 483 ms 587048 KB Output is correct
4 Correct 486 ms 582392 KB Output is correct
5 Correct 544 ms 604448 KB Output is correct
6 Correct 546 ms 603876 KB Output is correct
7 Correct 331 ms 486048 KB Output is correct
8 Correct 489 ms 556132 KB Output is correct
9 Correct 449 ms 544968 KB Output is correct
10 Correct 420 ms 540508 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 483660 KB Output is correct
2 Correct 297 ms 482632 KB Output is correct
3 Correct 296 ms 483012 KB Output is correct
4 Correct 291 ms 482388 KB Output is correct
5 Correct 290 ms 482720 KB Output is correct
6 Correct 297 ms 483516 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 479432 KB Output is correct
2 Correct 278 ms 479476 KB Output is correct
3 Correct 272 ms 479428 KB Output is correct
4 Correct 266 ms 479424 KB Output is correct
5 Correct 269 ms 479388 KB Output is correct
6 Correct 272 ms 479432 KB Output is correct
7 Correct 269 ms 479556 KB Output is correct
8 Correct 492 ms 576904 KB Output is correct
9 Correct 493 ms 575848 KB Output is correct
10 Correct 483 ms 587048 KB Output is correct
11 Correct 486 ms 582392 KB Output is correct
12 Correct 544 ms 604448 KB Output is correct
13 Correct 546 ms 603876 KB Output is correct
14 Correct 331 ms 486048 KB Output is correct
15 Correct 489 ms 556132 KB Output is correct
16 Correct 449 ms 544968 KB Output is correct
17 Correct 420 ms 540508 KB Output is correct
18 Correct 301 ms 483660 KB Output is correct
19 Correct 297 ms 482632 KB Output is correct
20 Correct 296 ms 483012 KB Output is correct
21 Correct 291 ms 482388 KB Output is correct
22 Correct 290 ms 482720 KB Output is correct
23 Correct 297 ms 483516 KB Output is correct
24 Correct 472 ms 561160 KB Output is correct
25 Correct 515 ms 563700 KB Output is correct
26 Correct 468 ms 559428 KB Output is correct
27 Correct 476 ms 566384 KB Output is correct
28 Correct 419 ms 503940 KB Output is correct
29 Correct 362 ms 488048 KB Output is correct