oj.uz

Submission #128823

# Submission time Handle Problem Language Result Execution time Memory
128823 2019-07-11T09:54:51 Z godwind Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 468 ms 187036 KB 
#pragma GCC optimize("Ofast")
/*#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
                         
using namespace std;
                         
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
                         
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}
   
#define ghost signed
#define left left228
#define right right228
#define prev prev228
#define list list228
  
const int N = 100 * 1000 + 228;
 
int code(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    return 3;
}
 
struct node
{
    int nxt[4];
    vector<int> list;
    int mn, mx;
    node() {
        nxt[0] = nxt[1] = nxt[2] = nxt[3] = 0;
        list.clear();
        mn = mx = 0;
    }
};
 
vector< node > t1, t;
int counter1 = 0, counter = 0;
 
void init() {
    t1.push_back(node());
    t.push_back(node());
}
 
void add1(string s, int i) {
    int now = 0;
    int c = 0;
    for (char C : s) {
        c = code(C);
        if (!t1[now].nxt[c]) {
            t1[now].nxt[c] = ++counter1;
            t1.push_back(node());
        }
        now = t1[now].nxt[c];
        if (t1[now].mn == 0) {
            t1[now].mn = t1[now].mx = i;
        } else {
            uin(t1[now].mn, i);
            uax(t1[now].mx, i);
        }
    }
}
 
pair<int, int> get_range(string s) {
    int now = 0;
    int c = 0;
    for (char C : s) {
        c = code(C);
        if (!t1[now].nxt[c]) return {0, 0};
        now = t1[now].nxt[c];
    }
    return {t1[now].mn, t1[now].mx};
}
 
void add(string s, int i) {
    int now = 0;
    int c = 0;
    for (char C : s) {
        c = code(C);
        if (!t[now].nxt[c]) {
            t[now].nxt[c] = ++counter;
            t.push_back(node());
        }
        now = t[now].nxt[c];
        t[now].list.push_back(i);
    }
}
 
int get(string s, int l, int r) {
    int now = 0;
    int c = 0;
    for (char C : s) {
        c = code(C);
        if (!t[now].nxt[c]) return 0;
        now = t[now].nxt[c];
    }
    int up = upper_bound(t[now].list.begin(), t[now].list.end(), r) - t[now].list.begin();
    int down = lower_bound(t[now].list.begin(), t[now].list.end(), l) - t[now].list.begin();
    return up - down;
}
 
string str[N];
int n, m;
 
 
ghost main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> str[i];
    }
    sort(str + 1, str + n + 1);
    init();
    for (int i = 1; i <= n; ++i) {
        add1(str[i], i);
        reverse(str[i].begin(), str[i].end());
        add(str[i], i);
    }
    for (int it = 0; it < m; ++it) {
        string p, q;
        cin >> p >> q;
        reverse(q.begin(), q.end());
        pair<int, int> range = get_range(p);
        if (range.first == 0) {
            cout << 0 << '\n';
            continue;
        }
        int l = range.first, r = range.second;
        cout << get(q, l, r) << '\n';
    }
    return 0;
} // kek ;
  
  
/*
  
8
1 2 4 1 3 4 1 2
2 2 3 2 2 3 2 2
  
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 163592 KB Output is correct
2 Correct 415 ms 155428 KB Output is correct
3 Correct 307 ms 112880 KB Output is correct
4 Correct 289 ms 112960 KB Output is correct
5 Correct 464 ms 186960 KB Output is correct
6 Correct 468 ms 187036 KB Output is correct
7 Correct 85 ms 19036 KB Output is correct
8 Correct 346 ms 135004 KB Output is correct
9 Correct 288 ms 117560 KB Output is correct
10 Correct 264 ms 104228 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4852 KB Output is correct
2 Correct 30 ms 5044 KB Output is correct
3 Correct 34 ms 4832 KB Output is correct
4 Correct 27 ms 4600 KB Output is correct
5 Correct 31 ms 4856 KB Output is correct
6 Correct 37 ms 4856 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3576 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 5 ms 3448 KB Output is correct
4 Correct 5 ms 3448 KB Output is correct
5 Correct 5 ms 3448 KB Output is correct
6 Correct 5 ms 3576 KB Output is correct
7 Correct 5 ms 3576 KB Output is correct
8 Correct 412 ms 163592 KB Output is correct
9 Correct 415 ms 155428 KB Output is correct
10 Correct 307 ms 112880 KB Output is correct
11 Correct 289 ms 112960 KB Output is correct
12 Correct 464 ms 186960 KB Output is correct
13 Correct 468 ms 187036 KB Output is correct
14 Correct 85 ms 19036 KB Output is correct
15 Correct 346 ms 135004 KB Output is correct
16 Correct 288 ms 117560 KB Output is correct
17 Correct 264 ms 104228 KB Output is correct
18 Correct 36 ms 4852 KB Output is correct
19 Correct 30 ms 5044 KB Output is correct
20 Correct 34 ms 4832 KB Output is correct
21 Correct 27 ms 4600 KB Output is correct
22 Correct 31 ms 4856 KB Output is correct
23 Correct 37 ms 4856 KB Output is correct
24 Correct 417 ms 139600 KB Output is correct
25 Correct 417 ms 139612 KB Output is correct
26 Correct 394 ms 139576 KB Output is correct
27 Correct 283 ms 113956 KB Output is correct
28 Correct 247 ms 35532 KB Output is correct
29 Correct 101 ms 12144 KB Output is correct