Submission #992016

#	Time	Username	Problem	Language	Result	Execution time	Memory
992016		saddd	Dabbeh (INOI20_dabbeh)	C++17	100 / 100	798 ms	111164 KiB

Main

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//#pragma GCC optimize("O3")
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
ll mod = 998244353, pr = 69;
const int mxn = 3e5 + 5, mxq = 1e5 + 5, sq = 1005, mxv = 5e4 + 1, lg = 60;
//const int base = (1 <<18);
const ll inf = 2e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rr(ll l, ll r){
    return(uniform_int_distribution<ll>(l, r)(rng));
}
// have fun!
struct Hash{
    vt<ll>hsh, pw;
    void init(string s){
        pw.resize(sz(s) + 1, 0); hsh.resize(sz(s) + 1, 0);
        for(int i = 0; i < sz(s); i++){
            hsh[i + 1] = (hsh[i] * pr + (s[i] - 'a' + 1)) % mod;
        }
        pw[0] = 1;
        for(int i = 1; i <= sz(s); i++){
            pw[i] = (pw[i - 1] * pr) % mod;
        }
    }
    ll get(int l, int r){
        return((hsh[r + 1] - hsh[l] * pw[r - l + 1] + mod * mod) % mod);
    }
};
Hash ht[mxn + 1], hs;
int n, m;
string t[mxn + 1], s;
pii get(int ids, int idt){
    int l = 1, r = min(sz(s) - ids, sz(t[idt])), ans = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(hs.get(ids, ids + mid - 1) == ht[idt].hsh[mid]){
            ans = mid; l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    if(ans == min(sz(s) - ids, sz(t[idt]))){
        return(mpp(ans, sz(s) - ids < sz(t[idt])));
    }else{
        return(mpp(ans, s[ids + ans] < t[idt][ans]));
    }
}
int up[mxn + 1][19];
pii mx[mxn + 1][19];
int getmx(int l, int r){
    int lg = __lg(r - l + 1);
    return(max(mx[l][lg], mx[r - (1 << lg) + 1][lg]).se);
}
void solve(){  
    cin >> n >> m;
    mod = rr(1e8, 1e9);
    for(int i = 1; i <= n; i++){
        cin >> t[i]; 
    }
    sort(t + 1, t + n + 1);
    for(int i = 1; i <= n; i++)ht[i].init(t[i]);
    cin >> s; hs.init(s);
    for(int i = 0; i < sz(s); i++){
        int l = 1, r = n, ans = 0;
        while(l <= r){
            int mid = (l + r) >> 1;
            
            pii cand = get(i, mid);
            ans = max(ans, cand.fi);
            if(cand.se == 0){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
            
        }
        up[i][0] = i + ans;
        mx[i][0] = mpp(up[i][0], i);
    }
    for(int i = 1; i < 19; i++){
        for(int j = 0; j + (1 << i) - 1 < sz(s); j++){
            mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]);
        }
    }
    up[sz(s)][0] = sz(s);
    for(int i = 1; i < 19; i++){
        deque<int>dq;
        for(int j = sz(s); j >= 0; j--){
            while(sz(dq) && up[j][i - 1] >= up[dq.back()][i - 1])dq.pop_back();
            dq.pb(j);
            int l = 0, r = sz(dq) - 1, ans;
            while(l <= r){
                int mid = (l + r) >> 1;
                if(dq[mid] <= up[j][i - 1]){
                    ans = mid; r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }
            up[j][i] = up[dq[ans]][i - 1];
        }
    }
    
    while(m--){
        int l, r; cin >> l >> r; r--;
        int ans = 0;
        for(int i = 18; i >= 0; i--){
            if(up[l][i] <= r){
                ans += (1 << i); l = getmx(l, up[l][i]);
            }
        }
        
        cout << ((ans == ((1 << 19) - 1)) ? -1 : ans + 1) << "\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("TESTROOMS.inp", "r", stdin);
    //freopen("TESTROOMS.out", "w", stdout);
    int tt; tt = 1;
    while(tt--){
        solve();
 
    }
    return(0);
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50