oj.uz

Submission #1002658

# Submission time Handle Problem Language Result Execution time Memory
1002658 2024-06-19T17:41:18 Z Huseyn123 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1160 ms 602252 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
  #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#define int ll
#define MAX 1000001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second 

#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << endl;\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << (int)x << " ";\
    }\
    cout << endl;\
}
#define reset(a,n,v){\
    for(int i=0;i<n;i++){\
        a[i]=v;\
    }\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
int n,q,t=1,m,k,x,y,z,x2,y2,z2,d[MAX],e[MAX];
long long a[MAX],b[MAX];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string s[MAX],str[MAX];
//int e[1001][1001];
string s1,s2,s3;
const int mod = 998244353;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int B1=133,B2=135,M1=1e9+7,M2=1e9+9; 
long long pow1[MAX],pow2[MAX];
int cost[501][501],can[501][501];
int get_hash_1(int l,int r){
    long long h=a[r];
    if(l!=0){
        h-=a[l-1];
    }
    if(h<0){
        h+=M1;
    }
    h*=pow1[l];
    h%=M1;
    return h;
}
int get_hash_2(int l,int r){
    long long h=b[r];
    if(l!=0){
        h-=b[l-1];
    }
    if(h<0){
        h+=M2;
    }
    h*=pow2[l];
    h%=M2;
    return h;
}
int N=500000;
vector<vector<int>> sp(20,vector<int>(300001));
int lg[MAX];
struct sp_tb{
    vector<vector<int>> sp;
    int sz;
    void init(int n){
        sp.resize(20,vector<int>(n)); 
        sz=n;
    }
    void build(vector<int> &a){
        for(int i=0;i<sz;i++){
            sp[0][i]=a[i];
        }
        for(int j=1;j<20;j++){
            for(int i=0;i+(1<<j)-1<sz;i++){
                sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
            }
        }
    }
    int get_max(int l,int r){
        int i=r-l+1;
        i=lg[i];
        return max(sp[i][l],sp[i][r-(1<<i)+1]);
    }
};
sp_tb st[20];
vector<vector<pll>> c(500001);
void solve(){
    cin >> n >> q;
    long long p1,p2;
    p1=p2=1;
    pow1[0]=pow2[0]=1;
    lg[0]=-1;
    for(int i=1;i<=N;i++){
        lg[i]=lg[i/2]+1;
        p1=p1*B1;
        p2=p2*B2;
        p1%=M1; 
        p2%=M2;
        pow1[i]=p1;
        pow2[i]=p2;
    }
    for(int i=0;i<n;i++){
        cin >> s[i];
        k=(int)s[i].size();
        long long h1,h2;
        h1=h2=0;
        for(int j=0;j<k;j++){
            h1+=(s[i][j]*pow1[N-j])%M1;
            h1%=M1; 
            h2+=(s[i][j]*pow2[N-j])%M2;
            h2%=M2;
            c[j+1].pb({h1,h2});
        }
    }
    for(int i=0;i<=N;i++){
        sortv(c[i]);
    }
    cin >> s1; 
    m=(int)s1.size();
    long long h1,h2; 
    h1=h2=0;
    for(int j=0;j<m;j++){
        h1+=(s1[j]*pow1[N-j])%M1;
        h1%=M1; 
        h2+=(s1[j]*pow2[N-j])%M2;
        h2%=M2;
        a[j]=h1; 
        b[j]=h2;
    }
    for(int j=0;j<m;j++){
        int l,r; 
        l=j;
        r=m-1;
        while(l<r){
            int mid=(l+r+1)/2; 
            pll p={get_hash_1(j,mid),get_hash_2(j,mid)};
            auto it=lb(c[mid-j+1],p);
            if(it!=c[mid-j+1].end() && (*it)==p){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        pll p={get_hash_1(j,l),get_hash_2(j,l)};
        auto it=lb(c[l-j+1],p);
        if(it!=c[l-j+1].end() && *it==p){
            d[j]=l;
        }
        else{
            d[j]=-1;
        }
        sp[0][j]=d[j];
    }
    st[0].init(m); 
    st[0].build(sp[0]);
    for(int i=1;i<20;i++){
        for(int j=0;j<m;j++){
            if(sp[i-1][j]==-1){
                sp[i][j]=-1;
                continue;
            }
            sp[i][j]=st[i-1].get_max(j,min(m-1,sp[i-1][j]+1));
        }
        st[i].init(m);
        st[i].build(sp[i]);
    } 
    for(int i=0;i<q;i++){
        cin >> x >> y;
        y--;
        int x1=x;
        int res=0;
        bool ok=false,ok1=false;
        if(sp[19][x]<y){
            ok1=true;
        }
        for(int j=19;j>=0;j--){
            if(!ok){
                //cout << x1 << " " << j << " " << sp[j][x] << "\n";
                if(sp[j][x]!=-1 && sp[j][x]<y){
                    res+=(1<<j);
                    x=sp[j][x];
                    ok=true;
                }
            }
            else{
                int h1=st[j].get_max(x1,min(m-1,x+1));
                //cout << x1 << " zor" << y  << " " << h1 << "\n";
                if(h1<y){
                    res+=(1<<j);
                    x=h1;
                }
            }
        }
        if(ok1){
            res=-2;
        }
        cout << res+1 << "\n";
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input13.txt","r",stdin);
    //cin >> t;
    ll cnt1=1;
    while(t--){
        solve();
        cnt1++; 
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 108056 KB Output is correct
2 Correct 121 ms 118852 KB Output is correct
3 Correct 119 ms 117784 KB Output is correct
4 Correct 138 ms 119956 KB Output is correct
5 Correct 138 ms 119584 KB Output is correct
6 Correct 144 ms 121652 KB Output is correct
7 Correct 133 ms 124600 KB Output is correct
8 Correct 141 ms 122280 KB Output is correct
9 Correct 132 ms 121272 KB Output is correct
10 Correct 111 ms 114356 KB Output is correct
11 Correct 116 ms 126144 KB Output is correct
12 Correct 99 ms 118464 KB Output is correct
13 Correct 105 ms 122560 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 589488 KB Output is correct
2 Correct 621 ms 592512 KB Output is correct
3 Correct 601 ms 590124 KB Output is correct
4 Correct 532 ms 588220 KB Output is correct
5 Correct 536 ms 588092 KB Output is correct
6 Correct 588 ms 592316 KB Output is correct
7 Correct 634 ms 593868 KB Output is correct
8 Correct 573 ms 591296 KB Output is correct
9 Correct 640 ms 592568 KB Output is correct
10 Correct 611 ms 594344 KB Output is correct
11 Correct 560 ms 590008 KB Output is correct
12 Correct 539 ms 589496 KB Output is correct
13 Correct 627 ms 595264 KB Output is correct
14 Correct 614 ms 594156 KB Output is correct
15 Correct 548 ms 587452 KB Output is correct
16 Correct 371 ms 599480 KB Output is correct
17 Correct 346 ms 589984 KB Output is correct
18 Correct 351 ms 589756 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 108056 KB Output is correct
2 Correct 121 ms 118852 KB Output is correct
3 Correct 119 ms 117784 KB Output is correct
4 Correct 138 ms 119956 KB Output is correct
5 Correct 138 ms 119584 KB Output is correct
6 Correct 144 ms 121652 KB Output is correct
7 Correct 133 ms 124600 KB Output is correct
8 Correct 141 ms 122280 KB Output is correct
9 Correct 132 ms 121272 KB Output is correct
10 Correct 111 ms 114356 KB Output is correct
11 Correct 116 ms 126144 KB Output is correct
12 Correct 99 ms 118464 KB Output is correct
13 Correct 105 ms 122560 KB Output is correct
14 Correct 620 ms 589488 KB Output is correct
15 Correct 621 ms 592512 KB Output is correct
16 Correct 601 ms 590124 KB Output is correct
17 Correct 532 ms 588220 KB Output is correct
18 Correct 536 ms 588092 KB Output is correct
19 Correct 588 ms 592316 KB Output is correct
20 Correct 634 ms 593868 KB Output is correct
21 Correct 573 ms 591296 KB Output is correct
22 Correct 640 ms 592568 KB Output is correct
23 Correct 611 ms 594344 KB Output is correct
24 Correct 560 ms 590008 KB Output is correct
25 Correct 539 ms 589496 KB Output is correct
26 Correct 627 ms 595264 KB Output is correct
27 Correct 614 ms 594156 KB Output is correct
28 Correct 548 ms 587452 KB Output is correct
29 Correct 371 ms 599480 KB Output is correct
30 Correct 346 ms 589984 KB Output is correct
31 Correct 351 ms 589756 KB Output is correct
32 Correct 644 ms 431804 KB Output is correct
33 Correct 659 ms 436340 KB Output is correct
34 Correct 733 ms 438604 KB Output is correct
35 Correct 640 ms 437180 KB Output is correct
36 Correct 652 ms 441016 KB Output is correct
37 Correct 617 ms 431512 KB Output is correct
38 Correct 1160 ms 600372 KB Output is correct
39 Correct 1088 ms 595812 KB Output is correct
40 Correct 1122 ms 602040 KB Output is correct
41 Correct 1047 ms 602252 KB Output is correct
42 Correct 1064 ms 597952 KB Output is correct
43 Correct 449 ms 278324 KB Output is correct
44 Correct 486 ms 277952 KB Output is correct
45 Correct 496 ms 277828 KB Output is correct
46 Correct 492 ms 281812 KB Output is correct
47 Correct 1041 ms 593004 KB Output is correct
48 Correct 1041 ms 596160 KB Output is correct
49 Correct 989 ms 593568 KB Output is correct
50 Correct 1156 ms 600268 KB Output is correct
51 Correct 546 ms 591736 KB Output is correct
52 Correct 453 ms 594832 KB Output is correct
53 Correct 583 ms 592016 KB Output is correct