oj.uz

Submission #468916

# Submission time Handle Problem Language Result Execution time Memory
468916 2021-08-30T07:43:36 Z amirmohammad_nezami Dabbeh (INOI20_dabbeh) C++14
25 / 100
 2000 ms 103316 KB 
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define lc 2 * v
#define rc 2 * v + 1
#define mid (s + e) / 2
#define PB push_back
#define ll long long 
#define ld long double
#define _sz(e) (int)e.size()
#define pii pair <int , int>
#define _all(e) e.begin() , e.end()
#define FAST ios::sync_with_stdio(0); cin.tie(0);

const ll maxn = 3e5 + 4 , N = 1e4 + 4 , base = 307 , mod = 1e9 + 7 , INF = 1e9 , lg = 19;

struct node {
    int mx[lg];
};

node seg[4 * maxn];

string t[N];
ll pbase[maxn];
vector <ll> h[N];
int n , m , ql[maxn] , qr[maxn] , SZ , res[maxn] , dp[lg][maxn];

void pre() {
    pbase[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        pbase[i] = (pbase[i - 1] * base) % mod;
    }
    for (int i = 0; i <= n; ++i) {
        h[i].PB(0);
        for (int j = 1; j <= _sz(t[i]); ++j) {
            int val = (h[i].back() * base + t[i][j - 1]) % mod;
            h[i].PB(val);
        }
    }
}

inline int HASH(int i , int l , int r) {
    return (h[i][r] - (h[i][l] * pbase[r - l] % mod) + mod) % mod;
}

inline int LCP(int x , int i) {
    if(t[0][x] != t[i][0]) return 0;
    int l = 1 , r = min(SZ - x , _sz(t[i])) + 1;
    while(l < r - 1) {
        int mm = (l + r) / 2;
        if(HASH(0 , x , x + mm) == HASH(i , 0 , mm)) l = mm;
        else r = mm;
    }
    return l;
}

inline bool check(int x , int i) {
    int lcp = LCP(x , i);
    if(x + lcp == SZ) return (_sz(t[i]) > lcp);
    if(_sz(t[i]) == lcp) return 0;
    return t[0][x + lcp] < t[i][lcp];
}

inline int bs(int x) {
    if(check(x , 1)) return 1;
    int l = 1 , r = n + 1;
    while(l < r - 1) {
        int mm = (l + r) / 2;
        if(check(x , mm)) r = mm;
        else l = mm;
    }
    return r;
}

void add(int i , int p , int x , int v = 1 , int s = 0 , int e = SZ) {
    seg[v].mx[i] = max(seg[v].mx[i] , x);
    if(e - s == 1) return ;
    if(p < mid) {
        add(i , p , x , lc , s , mid); 
        return ;
    }
    add(i , p , x , rc , mid , e);
}

int get(int i , int l , int r , int v = 1 , int s = 0 , int e = SZ) {
    if(l >= e || s >= r) return 0;
    if(l <= s && e <= r) return seg[v].mx[i];
    return max(get(i , l , r , lc , s , mid) , get(i , l , r , rc , mid , e));
}

int main() {
    FAST;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> t[i];
    }
    cin >> t[0];
    sort(t + 1 , t + 1 + n);
    for (int i = 0; i < m; ++i) {
        cin >> ql[i] >> qr[i]; 
    }
    pre();

    SZ = _sz(t[0]);
    for (int i = 0; i < SZ; ++i) {
        int p = bs(i);
        if(p <= n) dp[0][i] = max(dp[0][i] , i + LCP(i , p));
        if(p > 0) dp[0][i] = max(dp[0][i] , i + LCP(i , p - 1));
        add(0 , i , dp[0][i]);
    }

    for (int i = 1; i < lg; ++i) {
        for (int j = 0; j < SZ; ++j) {
            dp[i][j] = get(i - 1 , j , dp[i - 1][j] + 1);
            add(i , j , dp[i][j]);
        }
    }
    for (int i = 0; i < m; ++i) {
        int cost = 0 , mx = ql[i];
        for (int j = lg - 1; j >= 0; --j) {
            int idx = get(j , ql[i] , mx + 1);
            if(idx >= qr[i]) continue;
            cost += (1 << j) , mx = idx;
        }

        cout << (get(0 , ql[i] , mx + 1) >= qr[i] ? cost + 1 : -1) << '\n';
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 571 ms 11364 KB Output is correct
3 Correct 724 ms 10180 KB Output is correct
4 Correct 780 ms 11772 KB Output is correct
5 Correct 815 ms 10928 KB Output is correct
6 Correct 791 ms 12432 KB Output is correct
7 Correct 845 ms 11792 KB Output is correct
8 Correct 785 ms 12700 KB Output is correct
9 Correct 757 ms 11812 KB Output is correct
10 Correct 732 ms 7928 KB Output is correct
11 Correct 594 ms 10528 KB Output is correct
12 Correct 591 ms 8216 KB Output is correct
13 Correct 599 ms 10188 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 571 ms 11364 KB Output is correct
3 Correct 724 ms 10180 KB Output is correct
4 Correct 780 ms 11772 KB Output is correct
5 Correct 815 ms 10928 KB Output is correct
6 Correct 791 ms 12432 KB Output is correct
7 Correct 845 ms 11792 KB Output is correct
8 Correct 785 ms 12700 KB Output is correct
9 Correct 757 ms 11812 KB Output is correct
10 Correct 732 ms 7928 KB Output is correct
11 Correct 594 ms 10528 KB Output is correct
12 Correct 591 ms 8216 KB Output is correct
13 Correct 599 ms 10188 KB Output is correct
14 Execution timed out 2085 ms 103316 KB Time limit exceeded
15 Halted 0 ms 0 KB -