oj.uz

Submission #468885

# Submission time Handle Problem Language Result Execution time Memory
468885 2021-08-30T06:31:03 Z amirmohammad_nezami Dabbeh (INOI20_dabbeh) C++14
25 / 100
 1412 ms 25620 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] , pos[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) {
        pos[i] = bs(i);
        if(_sz(q[i])) {
            fill(seg , seg + 4 * SZ , INF);
            fill(dp , dp + SZ , INF);
            for (int j = i; j >= 0; --j) {
                int mx = 0;
                if(pos[j] <= n) mx = max(mx , LCP(j , pos[j]));
                if(pos[j] > 0) mx = max(mx , LCP(j , pos[j] - 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 7 ms 10188 KB Output is correct
2 Correct 96 ms 20176 KB Output is correct
3 Correct 112 ms 18872 KB Output is correct
4 Correct 130 ms 20536 KB Output is correct
5 Correct 148 ms 19764 KB Output is correct
6 Correct 143 ms 21304 KB Output is correct
7 Correct 147 ms 21176 KB Output is correct
8 Correct 149 ms 21720 KB Output is correct
9 Correct 152 ms 20692 KB Output is correct
10 Correct 170 ms 16844 KB Output is correct
11 Correct 127 ms 19776 KB Output is correct
12 Correct 135 ms 17604 KB Output is correct
13 Correct 123 ms 18884 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1313 ms 22340 KB Output is correct
2 Correct 1186 ms 24524 KB Output is correct
3 Correct 1090 ms 22684 KB Output is correct
4 Correct 1161 ms 21568 KB Output is correct
5 Correct 1321 ms 21720 KB Output is correct
6 Correct 443 ms 24364 KB Output is correct
7 Correct 407 ms 25304 KB Output is correct
8 Correct 415 ms 23928 KB Output is correct
9 Correct 497 ms 24764 KB Output is correct
10 Correct 565 ms 25620 KB Output is correct
11 Correct 1236 ms 22988 KB Output is correct
12 Incorrect 1412 ms 22596 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10188 KB Output is correct
2 Correct 96 ms 20176 KB Output is correct
3 Correct 112 ms 18872 KB Output is correct
4 Correct 130 ms 20536 KB Output is correct
5 Correct 148 ms 19764 KB Output is correct
6 Correct 143 ms 21304 KB Output is correct
7 Correct 147 ms 21176 KB Output is correct
8 Correct 149 ms 21720 KB Output is correct
9 Correct 152 ms 20692 KB Output is correct
10 Correct 170 ms 16844 KB Output is correct
11 Correct 127 ms 19776 KB Output is correct
12 Correct 135 ms 17604 KB Output is correct
13 Correct 123 ms 18884 KB Output is correct
14 Correct 1313 ms 22340 KB Output is correct
15 Correct 1186 ms 24524 KB Output is correct
16 Correct 1090 ms 22684 KB Output is correct
17 Correct 1161 ms 21568 KB Output is correct
18 Correct 1321 ms 21720 KB Output is correct
19 Correct 443 ms 24364 KB Output is correct
20 Correct 407 ms 25304 KB Output is correct
21 Correct 415 ms 23928 KB Output is correct
22 Correct 497 ms 24764 KB Output is correct
23 Correct 565 ms 25620 KB Output is correct
24 Correct 1236 ms 22988 KB Output is correct
25 Incorrect 1412 ms 22596 KB Output isn't correct
26 Halted 0 ms 0 KB -