oj.uz

Submission #1002660

# Submission time Handle Problem Language Result Execution time Memory
1002660 2024-06-19T17:42:22 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1234 ms 606380 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 68 ms 108064 KB Output is correct
2 Correct 140 ms 118976 KB Output is correct
3 Correct 134 ms 117552 KB Output is correct
4 Correct 150 ms 119992 KB Output is correct
5 Correct 152 ms 119484 KB Output is correct
6 Correct 152 ms 121532 KB Output is correct
7 Correct 148 ms 124604 KB Output is correct
8 Correct 156 ms 122048 KB Output is correct
9 Correct 141 ms 121436 KB Output is correct
10 Correct 122 ms 114200 KB Output is correct
11 Correct 128 ms 126024 KB Output is correct
12 Correct 128 ms 118464 KB Output is correct
13 Correct 121 ms 122560 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 589556 KB Output is correct
2 Correct 636 ms 592316 KB Output is correct
3 Correct 593 ms 596744 KB Output is correct
4 Correct 522 ms 587964 KB Output is correct
5 Correct 577 ms 587960 KB Output is correct
6 Correct 625 ms 592312 KB Output is correct
7 Correct 621 ms 593624 KB Output is correct
8 Correct 587 ms 591252 KB Output is correct
9 Correct 630 ms 592572 KB Output is correct
10 Correct 608 ms 594584 KB Output is correct
11 Correct 581 ms 590012 KB Output is correct
12 Correct 583 ms 589596 KB Output is correct
13 Correct 633 ms 595240 KB Output is correct
14 Correct 634 ms 594156 KB Output is correct
15 Correct 515 ms 587456 KB Output is correct
16 Correct 368 ms 599480 KB Output is correct
17 Correct 412 ms 590008 KB Output is correct
18 Correct 366 ms 589552 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 108064 KB Output is correct
2 Correct 140 ms 118976 KB Output is correct
3 Correct 134 ms 117552 KB Output is correct
4 Correct 150 ms 119992 KB Output is correct
5 Correct 152 ms 119484 KB Output is correct
6 Correct 152 ms 121532 KB Output is correct
7 Correct 148 ms 124604 KB Output is correct
8 Correct 156 ms 122048 KB Output is correct
9 Correct 141 ms 121436 KB Output is correct
10 Correct 122 ms 114200 KB Output is correct
11 Correct 128 ms 126024 KB Output is correct
12 Correct 128 ms 118464 KB Output is correct
13 Correct 121 ms 122560 KB Output is correct
14 Correct 660 ms 589556 KB Output is correct
15 Correct 636 ms 592316 KB Output is correct
16 Correct 593 ms 596744 KB Output is correct
17 Correct 522 ms 587964 KB Output is correct
18 Correct 577 ms 587960 KB Output is correct
19 Correct 625 ms 592312 KB Output is correct
20 Correct 621 ms 593624 KB Output is correct
21 Correct 587 ms 591252 KB Output is correct
22 Correct 630 ms 592572 KB Output is correct
23 Correct 608 ms 594584 KB Output is correct
24 Correct 581 ms 590012 KB Output is correct
25 Correct 583 ms 589596 KB Output is correct
26 Correct 633 ms 595240 KB Output is correct
27 Correct 634 ms 594156 KB Output is correct
28 Correct 515 ms 587456 KB Output is correct
29 Correct 368 ms 599480 KB Output is correct
30 Correct 412 ms 590008 KB Output is correct
31 Correct 366 ms 589552 KB Output is correct
32 Correct 641 ms 431548 KB Output is correct
33 Correct 716 ms 436164 KB Output is correct
34 Correct 700 ms 438352 KB Output is correct
35 Correct 675 ms 437236 KB Output is correct
36 Correct 668 ms 441084 KB Output is correct
37 Correct 641 ms 431532 KB Output is correct
38 Correct 1085 ms 600252 KB Output is correct
39 Correct 1072 ms 595392 KB Output is correct
40 Correct 1130 ms 602044 KB Output is correct
41 Correct 1031 ms 602268 KB Output is correct
42 Correct 1024 ms 598020 KB Output is correct
43 Correct 483 ms 278204 KB Output is correct
44 Correct 438 ms 277944 KB Output is correct
45 Correct 439 ms 277836 KB Output is correct
46 Correct 457 ms 282044 KB Output is correct
47 Correct 1083 ms 592924 KB Output is correct
48 Correct 1189 ms 595984 KB Output is correct
49 Correct 1188 ms 595328 KB Output is correct
50 Correct 1234 ms 606380 KB Output is correct
51 Correct 474 ms 591744 KB Output is correct
52 Correct 479 ms 596612 KB Output is correct
53 Correct 540 ms 591240 KB Output is correct