Submission #198630

#	Time	Username	Problem	Language	Result	Execution time	Memory
198630		Rakhmand	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	1593 ms	146172 KiB

selling_rna

//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)

const int MXN = 2e6 + 200;
const long long MNN = 1e5 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 500;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

//void istxt(bool yes){
//    if(yes == 1){
//        freopen("yinyang.in", "r", stdin);
//        freopen("yinyang.out", "w", stdout);
//    }else{
//        freopen("/Users/rakhmanabdirashov/Desktop/input.txt", "r", stdin);
//    }
//}

int n, sz = 0, rsz = 0, m, L, R, ans;
string s[MNN];

struct bor{
    int nx[4];
    int l, r;
    vector<int> v;
}t[MXN];

int trans(char ch){
    if(ch == 'A'){
        return 0;
    }else if(ch == 'U'){
        return 1;
    }else if(ch == 'G'){
        return 2;
    }else{
        return 3;
    }
}

void insert1(string s, int pos){
    int cur = 0;
    for(int i = 0; i < s.size(); i++){
        int letter = trans(s[i]);
        if(t[cur].nx[letter] == 0){
            t[cur].nx[letter] = ++sz;
            cur = sz;
            t[cur].l = t[cur].r = pos;
        }else{
            cur = t[cur].nx[letter];
            t[cur].r = pos;
        }
    }
}

void insert2(string s, int pos){
    int cur = 0;
    for(int i = 0; i < s.size(); i++){
        int letter = trans(s[i]);
        if(t[cur].nx[letter] == 0){
            t[cur].nx[letter] = ++sz;
            cur = sz;
            t[cur].v.push_back(pos);
        }else{
            cur = t[cur].nx[letter];
            t[cur].v.push_back(pos);
        }
    }
}

void get1(string s){
    int cur = 0;
    for(int i = 0; i < s.size(); i++){
        cur = t[cur].nx[trans(s[i])];
    }
    L = t[cur].l, R = t[cur].r;
}

int get2(string s){
    int cur = 0;
    for(int i = 0; i < s.size(); i++){
        cur = t[cur].nx[trans(s[i])];
    }
    int l = lower_bound(t[cur].v.begin(), t[cur].v.end(), L) - t[cur].v.begin();
    int r = upper_bound(t[cur].v.begin(), t[cur].v.end(), R) - t[cur].v.begin();
    return max(r - l, 0);
}

int main () {
    ios;
    //istxt(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> s[i];
    }
    sort(s + 1, s + n + 1);
    for(int i = 1; i <= n; i++){
        insert1(s[i], i);
        reverse(s[i].begin(), s[i].end());
        insert2(s[i], i);
    }
    for(int i = 1; i <= m; i++){
        string p, s;
        cin >> p >> s;
        get1(p);
        cout << get2(s) << nl;
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void insert1(std::__cxx11::string, int)':
selling_rna.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size(); i++){
                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'void insert2(std::__cxx11::string, int)':
selling_rna.cpp:100:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size(); i++){
                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'void get1(std::__cxx11::string)':
selling_rna.cpp:115:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size(); i++){
                    ~~^~~~~~~~~~
selling_rna.cpp: In function 'int get2(std::__cxx11::string)':
selling_rna.cpp:123:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size(); i++){
                    ~~^~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40