oj.uz

Submission #44676

# Submission time Handle Problem Language Result Execution time Memory
44676 2018-04-04T18:55:26 Z choikiwon Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 100852 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MN = 10000010;

int D[MN];
void radixSort(int *A, int *B, int *C, int N, int M) {
    for(int i = 0; i < M; i++) D[i] = 0;
    for(int i = 0; i < N; i++) D[ B[ A[i] ] ]++;
    for(int i = 1; i < M; i++) D[i] += D[i - 1];
    for(int i = N - 1; i >= 0; i--) C[ --D[ B[ A[i] ] ] ] = A[i];
}
int T[MN], B[MN];
void suffixArray(string &S, int *C, int N) {
    for(int i = 0; i < N; i++) {
        T[i] = i;
        B[i] = S[i];
    }
    radixSort(T, B, C, N, 128);
    for(int i = 1; i < N; i <<= 1) {
        int k = 0;
        for(int j = 0; j < i; j++) T[k++] = N - i + j;
        for(int j = 0; j < N; j++) if(C[j] >= i) T[k++] = C[j] - i;
        radixSort(T, B, C, N, N);
        T[ C[0] ] = k = 0;
        for(int j = 1; j < N; j++) {
            if(B[ C[j - 1] ] != B[ C[j] ] || B[ C[j - 1] + i ] != B[ C[j] + i ]) k++;
            T[ C[j] ] = k;
        }
        for(int j = 0; j < N; j++) B[j] = T[j];
    }
}
int R[MN];
void lcp(string &S, int *C, int *L, int N) {
    for(int i = 0; i < N; i++) R[ C[i] ] = i;
    for(int i = 0, h = 0; i < N; i++) {
        if(R[i]) {
            while(S[i + h] == S[ C[ R[i] - 1 ] + h ]) h++;
            L[ R[i] ] = h;
        }
        if(h) h--;
    }
}

int N, M, K;
string S;
int C[MN], L[MN], Q[100010], X[100010];

void getStr(string &s) {
    while(1) {
        char c = getchar();
        if(c == ' ' || c == '\n') break;
        s.push_back(c);
    }
}

int psum[MN];

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4 * K);
        build(0, K - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n] = L[l];
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = min(tree[2*n], tree[2*n + 1]);
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 1e9;
        if(a <= l && r <= b) return tree[n];
        int m = (l + r)>>1;
        int ll = quer(a, b, l, m, 2*n);
        int rr = quer(a, b, m + 1, r, 2*n + 1);
        return min(ll, rr);
    }
} bit;

int main() {
    scanf("%d %d", &N, &M);

    //*
    getchar();
    for(int i = 0; i < N; i++) {
        string s; getStr(s);

        S += s;
        S += '#';
        S += s;
        S += '@';
    }

    for(int i = 0; i < M; i++) {
        string p, q;
        getStr(p);
        getStr(q);

        Q[i] = S.size();
        X[i] = q.size() + p.size() + 1;
        S += q;
        S += '#';
        S += p;
        S += '@';
    }
    //*/

    K = S.size();
    suffixArray(S, C, K);
    lcp(S, C, L, K);
    
    if(K > 1000000) exit(0);

    for(int i = 0; i < K; i++) {
        psum[i] = C[i] < Q[0];
        if(i) psum[i] += psum[i - 1];
    }

    bit.init();
    for(int i = 0; i < M; i++) {
        int p = R[ Q[i] ];

        int s = 1, e = p, t1 = p + 1, t2 = p;
        while(s <= e) {
            int m = (s + e)>>1;

            if(bit.quer(m, p, 0, K - 1, 1) >= X[i]) {
                t1 = m;
                e = m - 1;
            }
            else s = m + 1;
        }
        s = p + 1, e = K - 1;
        while(s <= e) {
            int m = (s + e)>>1;

            if(bit.quer(p + 1, m, 0, K - 1, 1) >= X[i]) {
                t2 = m;
                s = m + 1;
            }
            else e = m - 1;
        }

        t1--;
        int ans = 0;
        ans += psum[p] - (t1? psum[t1 - 1] : 0);
        ans += psum[t2] - psum[p];
        printf("%d\n", ans);
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Correct 2 ms 692 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 3 ms 696 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1576 ms 100852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1048 ms 100852 KB Output is correct
2 Correct 703 ms 100852 KB Output is correct
3 Correct 930 ms 100852 KB Output is correct
4 Correct 810 ms 100852 KB Output is correct
5 Correct 744 ms 100852 KB Output is correct
6 Correct 929 ms 100852 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Correct 2 ms 692 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 3 ms 696 KB Output is correct
8 Execution timed out 1576 ms 100852 KB Time limit exceeded
9 Halted 0 ms 0 KB -