oj.uz

Submission #445830

# Submission time Handle Problem Language Result Execution time Memory
445830 2021-07-19T19:39:28 Z JovanB Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 754 ms 819016 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][26];

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];
        trie_add(1, i, s[i]);
    }
    for(int i=1; i<=m; i++){
        cin >> qpref[i] >> qsuf[i];
        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 333 ms 479492 KB Output is correct
2 Correct 279 ms 479444 KB Output is correct
3 Correct 276 ms 479428 KB Output is correct
4 Correct 274 ms 479404 KB Output is correct
5 Correct 278 ms 479412 KB Output is correct
6 Correct 276 ms 479604 KB Output is correct
7 Correct 282 ms 479428 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 746600 KB Output is correct
2 Correct 607 ms 736452 KB Output is correct
3 Correct 632 ms 754280 KB Output is correct
4 Correct 612 ms 741336 KB Output is correct
5 Correct 754 ms 813988 KB Output is correct
6 Correct 720 ms 819016 KB Output is correct
7 Correct 346 ms 491696 KB Output is correct
8 Correct 594 ms 684932 KB Output is correct
9 Correct 561 ms 653680 KB Output is correct
10 Correct 512 ms 643904 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 483768 KB Output is correct
2 Correct 315 ms 482788 KB Output is correct
3 Correct 319 ms 483256 KB Output is correct
4 Correct 313 ms 482344 KB Output is correct
5 Correct 320 ms 483080 KB Output is correct
6 Correct 326 ms 483628 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 479492 KB Output is correct
2 Correct 279 ms 479444 KB Output is correct
3 Correct 276 ms 479428 KB Output is correct
4 Correct 274 ms 479404 KB Output is correct
5 Correct 278 ms 479412 KB Output is correct
6 Correct 276 ms 479604 KB Output is correct
7 Correct 282 ms 479428 KB Output is correct
8 Correct 699 ms 746600 KB Output is correct
9 Correct 607 ms 736452 KB Output is correct
10 Correct 632 ms 754280 KB Output is correct
11 Correct 612 ms 741336 KB Output is correct
12 Correct 754 ms 813988 KB Output is correct
13 Correct 720 ms 819016 KB Output is correct
14 Correct 346 ms 491696 KB Output is correct
15 Correct 594 ms 684932 KB Output is correct
16 Correct 561 ms 653680 KB Output is correct
17 Correct 512 ms 643904 KB Output is correct
18 Correct 325 ms 483768 KB Output is correct
19 Correct 315 ms 482788 KB Output is correct
20 Correct 319 ms 483256 KB Output is correct
21 Correct 313 ms 482344 KB Output is correct
22 Correct 320 ms 483080 KB Output is correct
23 Correct 326 ms 483628 KB Output is correct
24 Correct 593 ms 703520 KB Output is correct
25 Correct 612 ms 706136 KB Output is correct
26 Correct 580 ms 700220 KB Output is correct
27 Correct 597 ms 706880 KB Output is correct
28 Correct 466 ms 526052 KB Output is correct
29 Correct 382 ms 491384 KB Output is correct