oj.uz

Submission #468883

# Submission time Handle Problem Language Result Execution time Memory
468883 2021-08-30T06:26:16 Z amirmohammad_nezami Dabbeh (INOI20_dabbeh) C++14
25 / 100
 2000 ms 23368 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 = 107 , mod = 1e9 + 7 , INF = 1e9;

ll pbase[maxn];
int n , m , SZ , res[maxn] , dp[maxn] , seg[4 * maxn];
string t[N];
vector <ll> h[N];
vector <pii> q[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 p , int x , int v = 1 , int s = 0 , int e = SZ) {
    seg[v] = min(seg[v] , x);
    if(e - s == 1) return ;
    if(p < mid) {
        add(p , x , lc , s , mid); 
        return ;
    }
    add(p , x , rc , mid , e);
}

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

int32_t 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) {
        int l , r; cin >> l >> r; r--;
        q[r].PB({l , i});
    }
    pre();

    SZ = _sz(t[0]);
    for (int i = 0; i < SZ; ++i) {
        if(_sz(q[i])) {
            fill(seg , seg + 4 * SZ , INF);
            fill(dp , dp + SZ , INF);
            for (int j = i; j >= 0; --j) {
                int pos = bs(j) , mx = 0;
                if(pos <= n) mx = max(mx , LCP(j , pos));
                if(pos > 0) mx = max(mx , LCP(j , pos - 1));
                dp[j] = (mx >= i - j + 1 ? 1 : get(j + 1 , j + mx + 1) + 1);
                add(j , dp[j]);
            }
            for (auto x : q[i]) {
                res[x.S] = dp[x.F];
            }
        }
    }

    for (int i = 0; i < m; ++i) {
        cout << (res[i] >= INF ? -1 : res[i]) << '\n';
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10188 KB Output is correct
2 Correct 101 ms 20060 KB Output is correct
3 Correct 142 ms 18780 KB Output is correct
4 Correct 211 ms 20524 KB Output is correct
5 Correct 234 ms 19744 KB Output is correct
6 Correct 304 ms 21368 KB Output is correct
7 Correct 185 ms 21172 KB Output is correct
8 Correct 289 ms 21828 KB Output is correct
9 Correct 300 ms 23368 KB Output is correct
10 Correct 255 ms 19176 KB Output is correct
11 Correct 140 ms 22288 KB Output is correct
12 Correct 133 ms 20024 KB Output is correct
13 Correct 162 ms 21424 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 21020 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 101 ms 20060 KB Output is correct
3 Correct 142 ms 18780 KB Output is correct
4 Correct 211 ms 20524 KB Output is correct
5 Correct 234 ms 19744 KB Output is correct
6 Correct 304 ms 21368 KB Output is correct
7 Correct 185 ms 21172 KB Output is correct
8 Correct 289 ms 21828 KB Output is correct
9 Correct 300 ms 23368 KB Output is correct
10 Correct 255 ms 19176 KB Output is correct
11 Correct 140 ms 22288 KB Output is correct
12 Correct 133 ms 20024 KB Output is correct
13 Correct 162 ms 21424 KB Output is correct
14 Execution timed out 2079 ms 21020 KB Time limit exceeded
15 Halted 0 ms 0 KB -