oj.uz

Submission #276348

# Submission time Handle Problem Language Result Execution time Memory
276348 2020-08-20T12:16:36 Z anonymous Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 484 ms 67320 KB 
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#define MAXL 2000005
#define MAXN 100005
using namespace std;
int ord(char c) {
    if (c == 'A') {return(0);}
    if (c == 'C') {return(1);}
    if (c == 'G') {return(2);}
    if (c == 'U') {return(3);}
}

int N, M;
string S[MAXN]; //strands
string qp, qs;

class Trie {
    int Nxt[MAXL][4], Preord[MAXL][2], ptr = 2, time=1;
public:
    void add(int id, int ind, int cur, bool b) { //b=0 means add front to back
        if (ind == S[id].size() || ind == -1) {return;}
        if (Nxt[cur][ord(S[id][ind])] == 0) {
            Nxt[cur][ord(S[id][ind])] = ptr++;
        }
        add(id, ind + (b ? -1 : 1), Nxt[cur][ord(S[id][ind])], b);
    }
    void preorder(int u) {
        Preord[u][0] = time++;
        for (int i=0; i<4; i++) {
            if (Nxt[u][i]) {preorder(Nxt[u][i]);}
        }
        Preord[u][1] = time - 1;
    }
    pair <int,int> ask(string &q, int ind, int cur, bool b) {
        if (!cur) {return(pair <int,int> {0,0});}
        if (ind == q.size() || ind == -1) {return(pair <int,int> {Preord[cur][0], Preord[cur][1]});}
        return(ask(q, ind+ + (b ? -1 : 1), Nxt[cur][ord(q[ind])], b));
    }
} TriP, TriS;

class PersistentSegtree {
    int ST[MAXN * 40][3]; //sum, L, R
    int Rt[MAXN], P[MAXN], ptr = 2, ptroot = 1;
public:
    int upd(int ind, int l, int r, int cur) {
        if (ind < l || ind > r) {return(cur);}
        if (l == r) {
            ST[ptr][0] = ST[cur][0] + 1;
            return(ptr++);
        } else {
            int tmp = ptr++, mid = (l + r) >> 1;
            ST[tmp][1] = upd(ind, l, mid, ST[cur][1]);
            ST[tmp][2] = upd(ind, mid+1, r, ST[cur][2]);
            ST[tmp][0] = ST[ST[tmp][1]][0] + ST[ST[tmp][2]][0];
            return(tmp);
        }
    }

    int ask(int lo, int hi, int l, int r, int cur) {
        if (!cur || lo > r || hi < l) {return(0);}
        if (lo <= l && hi >= r) {return(ST[cur][0]);}
        int mid = (l + r) >> 1;
        return(ask(lo, hi, l, mid, ST[cur][1])+
               ask(lo, hi, mid+1, r, ST[cur][2]));
    }

    void add(int x, int y) {
        P[ptroot] = x;
        Rt[ptroot] = upd(y, 1, MAXL, Rt[ptroot-1]);
        ptroot++;
    }
    int ub(int x) { //find largest less
        int lo = 0, hi = ptroot;
        while (lo + 1 != hi) {
            int mid = (lo + hi) >> 1;
            if (P[mid] < x) {lo = mid;}
            else {hi = mid;}
        }
        return(lo);
    }
    int Sum(int lox, int loy, int hix, int hiy) {
        int q1 = ub(lox), q2 = ub(hix+1);
        return(ask(loy, hiy, 1, MAXL, Rt[q2])-
               ask(loy, hiy, 1, MAXL, Rt[q1]));
    }
} PST;

vector <pair<int,int> > Pts;

int main() {
    cin.tie(0);
    //freopen("rnain.txt","r",stdin);
    cin >> N >> M;
    for (int i=1; i<=N; i++) {
        cin >> S[i];
        TriP.add(i, 0, 1, 0);
        TriS.add(i, S[i].size()-1, 1, 1);
    }

    TriP.preorder(1);
    TriS.preorder(1);
    for (int i=1; i<=N; i++) {
        pair <int,int> r1 = TriP.ask(S[i], 0, 1, 0), r2 = TriS.ask(S[i], S[i].size()-1, 1, 1);
        Pts.push_back({r1.first, r2.first});
    }
    sort(Pts.begin(), Pts.end());
    for (int i=0; i<Pts.size(); i++) {
        PST.add(Pts[i].first, Pts[i].second);
    }

    for (int i=0; i<M; i++) {
        cin >> qp >> qs;
        pair <int,int> xrange = TriP.ask(qp, 0, 1, 0), yrange = TriS.ask(qs, qs.size()-1, 1, 1);
        printf("%d\n",PST.Sum(xrange.first, yrange.first, xrange.second, yrange.second));
    }
}

Compilation message

selling_rna.cpp: In member function 'void Trie::add(int, int, int, bool)':
selling_rna.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         if (ind == S[id].size() || ind == -1) {return;}
      |             ~~~~^~~~~~~~~~~~~~~
selling_rna.cpp: In member function 'std::pair<int, int> Trie::ask(std::string&, int, int, bool)':
selling_rna.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if (ind == q.size() || ind == -1) {return(pair <int,int> {Preord[cur][0], Preord[cur][1]});}
      |             ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i=0; i<Pts.size(); i++) {
      |                   ~^~~~~~~~~~~
selling_rna.cpp: In function 'int ord(char)':
selling_rna.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
   14 | }
      | ^

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 57416 KB Output is correct
2 Correct 323 ms 55672 KB Output is correct
3 Correct 354 ms 57208 KB Output is correct
4 Correct 337 ms 55288 KB Output is correct
5 Correct 315 ms 66368 KB Output is correct
6 Correct 347 ms 67320 KB Output is correct
7 Correct 310 ms 11640 KB Output is correct
8 Correct 419 ms 46836 KB Output is correct
9 Correct 380 ms 41336 KB Output is correct
10 Correct 245 ms 38312 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 18032 KB Output is correct
2 Correct 79 ms 12404 KB Output is correct
3 Correct 79 ms 15216 KB Output is correct
4 Correct 68 ms 13296 KB Output is correct
5 Correct 67 ms 12480 KB Output is correct
6 Correct 85 ms 15188 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3712 KB Output is correct
2 Correct 3 ms 3584 KB Output is correct
3 Correct 3 ms 3584 KB Output is correct
4 Correct 3 ms 3584 KB Output is correct
5 Correct 3 ms 3584 KB Output is correct
6 Correct 3 ms 3584 KB Output is correct
7 Correct 3 ms 3584 KB Output is correct
8 Correct 330 ms 57416 KB Output is correct
9 Correct 323 ms 55672 KB Output is correct
10 Correct 354 ms 57208 KB Output is correct
11 Correct 337 ms 55288 KB Output is correct
12 Correct 315 ms 66368 KB Output is correct
13 Correct 347 ms 67320 KB Output is correct
14 Correct 310 ms 11640 KB Output is correct
15 Correct 419 ms 46836 KB Output is correct
16 Correct 380 ms 41336 KB Output is correct
17 Correct 245 ms 38312 KB Output is correct
18 Correct 90 ms 18032 KB Output is correct
19 Correct 79 ms 12404 KB Output is correct
20 Correct 79 ms 15216 KB Output is correct
21 Correct 68 ms 13296 KB Output is correct
22 Correct 67 ms 12480 KB Output is correct
23 Correct 85 ms 15188 KB Output is correct
24 Correct 341 ms 51196 KB Output is correct
25 Correct 377 ms 51576 KB Output is correct
26 Correct 320 ms 50680 KB Output is correct
27 Correct 334 ms 50680 KB Output is correct
28 Correct 484 ms 44044 KB Output is correct
29 Correct 363 ms 34664 KB Output is correct