Submission #276348

#	Time	Username	Problem	Language	Result	Execution time	Memory
276348		anonymous	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	484 ms	67320 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40