oj.uz

Submission #468909

# Submission time Handle Problem Language Result Execution time Memory
468909 2021-08-30T07:38:44 Z amirmohammad_nezami Dabbeh (INOI20_dabbeh) C++14
25 / 100
 2000 ms 115424 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];
vector <pii> q[maxn];
int n , m , ql[maxn] , qr[maxn] , SZ , res[maxn] , dp[maxn][lg];

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[i][0] = max(dp[i][0] , i + LCP(i , p));
        if(p > 0) dp[i][0] = max(dp[i][0] , i + LCP(i , p - 1));
        add(0 , i , dp[i][0]);
    }

    for (int i = 1; i < lg; ++i) {
        for (int j = 0; j < SZ; ++j) {
            dp[j][i] = get(i - 1 , j , dp[j][i - 1] + 1);
            add(i , j , dp[j][i]);
        }
    }
    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 8 ms 10188 KB Output is correct
2 Correct 559 ms 18324 KB Output is correct
3 Correct 756 ms 17088 KB Output is correct
4 Correct 790 ms 18628 KB Output is correct
5 Correct 815 ms 18012 KB Output is correct
6 Correct 806 ms 19720 KB Output is correct
7 Correct 819 ms 19008 KB Output is correct
8 Correct 776 ms 19888 KB Output is correct
9 Correct 745 ms 18752 KB Output is correct
10 Correct 715 ms 14916 KB Output is correct
11 Correct 645 ms 17448 KB Output is correct
12 Correct 600 ms 15368 KB Output is correct
13 Correct 610 ms 17288 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10188 KB Output is correct
2 Correct 559 ms 18324 KB Output is correct
3 Correct 756 ms 17088 KB Output is correct
4 Correct 790 ms 18628 KB Output is correct
5 Correct 815 ms 18012 KB Output is correct
6 Correct 806 ms 19720 KB Output is correct
7 Correct 819 ms 19008 KB Output is correct
8 Correct 776 ms 19888 KB Output is correct
9 Correct 745 ms 18752 KB Output is correct
10 Correct 715 ms 14916 KB Output is correct
11 Correct 645 ms 17448 KB Output is correct
12 Correct 600 ms 15368 KB Output is correct
13 Correct 610 ms 17288 KB Output is correct
14 Execution timed out 2081 ms 115424 KB Time limit exceeded
15 Halted 0 ms 0 KB -