oj.uz

Submission #468905

# Submission time Handle Problem Language Result Execution time Memory
468905 2021-08-30T07:33:59 Z amirmohammad_nezami Dabbeh (INOI20_dabbeh) C++14
25 / 100
 2000 ms 115456 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) {
            if(get(j , ql[i] , mx + 1) >= qr[i]) continue;
            cost += (1 << j) , mx = get(j , ql[i] , mx + 1);
        }

        int idx = get(0 , ql[i] , mx + 1);
        cout << (idx >= 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 544 ms 18220 KB Output is correct
3 Correct 738 ms 17112 KB Output is correct
4 Correct 828 ms 18888 KB Output is correct
5 Correct 873 ms 18244 KB Output is correct
6 Correct 844 ms 19884 KB Output is correct
7 Correct 834 ms 19160 KB Output is correct
8 Correct 785 ms 20148 KB Output is correct
9 Correct 785 ms 21436 KB Output is correct
10 Correct 747 ms 17192 KB Output is correct
11 Correct 627 ms 20116 KB Output is correct
12 Correct 635 ms 17632 KB Output is correct
13 Correct 642 ms 19788 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 115456 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 544 ms 18220 KB Output is correct
3 Correct 738 ms 17112 KB Output is correct
4 Correct 828 ms 18888 KB Output is correct
5 Correct 873 ms 18244 KB Output is correct
6 Correct 844 ms 19884 KB Output is correct
7 Correct 834 ms 19160 KB Output is correct
8 Correct 785 ms 20148 KB Output is correct
9 Correct 785 ms 21436 KB Output is correct
10 Correct 747 ms 17192 KB Output is correct
11 Correct 627 ms 20116 KB Output is correct
12 Correct 635 ms 17632 KB Output is correct
13 Correct 642 ms 19788 KB Output is correct
14 Execution timed out 2099 ms 115456 KB Time limit exceeded
15 Halted 0 ms 0 KB -