oj.uz

Submission #468903

# Submission time Handle Problem Language Result Execution time Memory
468903 2021-08-30T07:28:07 Z amirmohammad_nezami Dabbeh (INOI20_dabbeh) C++14
0 / 100
 2000 ms 115732 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]);
        // cout << dp[i][0] << ' ';
    }
    // cout << endl;
    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) {
            if(dp[mx][j] >= qr[i]) continue;
            cost += (1 << j) , mx = dp[mx][j];
        }
        // cout << cost << ' ' << mx << endl;
        int idx = get(0 , ql[i] , mx + 1);
        cout << (idx >= qr[i] ? cost + 1 : -1) << '\n';
    }
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10188 KB Output is correct
2 Correct 158 ms 18624 KB Output is correct
3 Incorrect 171 ms 17336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10188 KB Output is correct
2 Correct 158 ms 18624 KB Output is correct
3 Incorrect 171 ms 17336 KB Output isn't correct
4 Halted 0 ms 0 KB -