oj.uz

Submission #242117

# Submission time Handle Problem Language Result Execution time Memory
242117 2020-06-26T21:08:30 Z rqi Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 319472 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

#define f first
#define s second
#define mp make_pair
#define sz(x) (int)x.size()
#define pb push_back
#define ins insert

const int MOD = 1e9+7;
const int mx = 200005;

int b[2];
int ib[2];

int modpow(int b, ll p){
    int val = 1;
    for(ll g = b; p > 0; g = (g*g) % MOD){
        if(p % 2 == 1){
            val = (g*val) % MOD;
        }
        p/=2;
    }
    return val;
}

struct HashRange {
    int n;
    string S;
    vi csum[2];
    vi pows[2];
    vi ipows[2];
    HashRange(){

    }

    void init(string _S){
        n = sz(_S);
        S = "#"+_S;
        csum[0] = csum[1] = pows[0] = pows[1] = ipows[0] = ipows[1] = vi(n+1, 0);
        pows[0][0] = pows[1][0] = ipows[0][0] = ipows[1][0] = 1;
        pows[0][1] = b[0];
        pows[1][1] = b[1];
        ipows[0][1] = ib[0];
        ipows[1][1] = ib[1];
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < 2; j++){
                pows[j][i] = (ll(pows[j][i-1])*b[j]) % MOD;
                ipows[j][i] = (ll(ipows[j][i-1])*ib[j]) % MOD;
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < 2; j++){
                csum[j][i] = (ll(csum[j][i-1]) + ll(pows[j][i])*int(S[i])) % MOD;
            }
        }
    }

    ll hash(int l, int r){
        r++;
        int val0 = ((ll(csum[0][r])-csum[0][l])*ipows[0][l]) % MOD;
        int val1 = ((ll(csum[1][r])-csum[1][l])*ipows[1][l]) % MOD;
        val0 = (val0+MOD) % MOD;
        val1 = (val1+MOD) % MOD;
        return ll(val0)*MOD + val1;
    }
};

int N, M;
string S[mx];
HashRange Shash[mx];
HashRange Phash[mx];
HashRange Qhash[mx];
string P[mx];
string Q[mx];
pi rang[mx]; // range of P for each query
map<ll, int> m;
vi poses[mx];

bool Sless(int a, int b){
    if(S[a][0] != S[b][0]){
        return S[a][0] < S[b][0];
    }

    int lo = 1;
    int hi = min(sz(S[a]), sz(S[b]));
    while(lo < hi){
        int mid = (lo+hi)/2+1;
        if(Shash[a].hash(0, mid-1) == Shash[b].hash(0, mid-1)){
            lo = mid;
        }
        else hi = mid-1;
    }

    if(lo == sz(S[a]) && lo == sz(S[b])){
        return false;
    }
    
    if(lo == sz(S[a])){
        return true;
    }

    if(lo == sz(S[b])){
        return false;
    }
    
    return S[a][lo] < S[b][lo];
}

bool Pcmpless(int p, int s){ //P[p] <= S[s]
    if(P[p][0] != S[s][0]){
        return P[p][0] <= S[s][0];
    }

    int lo = 1;
    int hi = min(sz(P[p]), sz(S[s]));
    while(lo < hi){
        int mid = (lo+hi)/2+1;
        if(Phash[p].hash(0, mid-1) == Shash[s].hash(0, mid-1)){
            lo = mid;
        }
        else hi = mid-1;
    }

    if(lo == sz(P[p]) && lo == sz(S[s])){
        return true;
    }
    
    if(lo == sz(P[p])){
        return true;
    }

    if(lo == sz(S[s])){
        return false;
    }
    
    return P[p][lo] <= S[s][lo];
}

bool Pcmpgreat(int p, int s){ //P[p] >= S[s]
    if(P[p][0] != S[s][0]){
        return P[p][0] >= S[s][0];
    }

    int lo = 1;
    int hi = min(sz(P[p]), sz(S[s]));
    while(lo < hi){
        int mid = (lo+hi)/2+1;
        if(Phash[p].hash(0, mid-1) == Shash[s].hash(0, mid-1)){
            lo = mid;
        }
        else hi = mid-1;
    }

    if(lo == sz(P[p]) && lo == sz(S[s])){
        return true;
    }

    if(lo == sz(P[p])){
        return false;
    }

    if(lo == sz(S[s])){
        return true;
    }
    
    return P[p][lo] >= S[s][lo];
}

void ps(int a){
    cout << a << "\n";
}

int main(){
    b[0] = rand() % (MOD/5*4) + MOD/10;
    b[1] = rand() % (MOD/5*4) + MOD/10;
    ib[0] = modpow(b[0], MOD-2);
    ib[1] = modpow(b[1], MOD-2);
    
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        cin >> S[i];
        Shash[i].init(S[i]);
    }
    for(int i = 1; i <= M; i++){
        cin >> P[i] >> Q[i];
        Phash[i].init(P[i]);
        Qhash[i].init(Q[i]);
    }

    //make a hash struct for pair of ints -- DONE

    // HashRange a;
    // a.init("ABCABCABC");
    // cout << a.hash(0, 2).f << " " << a.hash(0, 2).s << "\n";
    // cout << a.hash(1, 3).f << " " << a.hash(1, 3).s << "\n";
    // cout << a.hash(3, 5).f << " " << a.hash(3, 5).s << "\n";
    
    //sort all S strings -- DONE
    vi Sstrs;
    for(int i = 1; i <= N; i++){
        Sstrs.pb(i);
    }

    sort(Sstrs.begin(), Sstrs.end(), [](int a, int b){return Sless(a, b);}); //maybe can't compare equals?
    vector<string> Shelp(N+1);
    for(int i = 0; i < N; i++){
        Shelp[i+1] = S[Sstrs[i]];
    }

    for(int i = 1; i <= N; i++){
        S[i] = Shelp[i];
        Shash[i].init(S[i]);
        //cout << S[i] << "\n"; --> should be sorted
    }

    //Each P[i] is a range of S, Q[i] --> hash val. Edit rang
    for(int i = 1; i <= M; i++){
        if(Pcmpless(i, N) == false){
            rang[i].f = N+1;
            continue;
        }
        int lo = 1;
        int hi = N;
        
        while(lo < hi){
            int mid = (lo+hi)/2;
            if(Pcmpless(i, mid)){
                hi = mid;
            }
            else lo = mid+1;
        }
        
        if(sz(S[lo]) < sz(P[i]) || Shash[lo].hash(0, sz(P[i])-1) != Phash[i].hash(0, sz(P[i])-1)){
            rang[i].f = N+1;
            continue;
        }

        rang[i].f = lo;
        hi = N;
        while(lo < hi){
            int mid = (lo+hi)/2+1;
            if(sz(S[mid]) < sz(P[i]) || Shash[mid].hash(0, sz(P[i])-1) != Phash[i].hash(0, sz(P[i])-1)){
                hi = mid-1;
            }
            else lo = mid;
        }
        rang[i].s = lo;
    }

    //Go through every suffix, if it's relevant insert index into a vector
    for(int i = 1; i <= M; i++){
        m[Qhash[i].hash(0, sz(Q[i])-1)];
    }

    int cnt = 0;
    for(auto &u: m){
        u.s = ++cnt;
    }

    for(int i = 1; i <= N; i++){
        for(int j = sz(S[i])-1; j >= 0; j--){
            if(m.count(Shash[i].hash(j, sz(S[i])-1))){
                poses[m[Shash[i].hash(j, sz(S[i])-1)]].pb(i);
            }
        }
    }

    //for every range and Q[i], binary search for # of suffixes that work for each 

    for(int i = 1; i <= M; i++){
        pi r = rang[i];
        int vind = m[Qhash[i].hash(0, sz(Q[i])-1)];
        int ans = 0;
        if(sz(poses[vind]) == 0 || r.s < poses[vind][0] || r.f > poses[vind].back()){
            ps(0);
            continue;
        }
        pi works;
        int lo = 0;
        int hi = sz(poses[vind])-1;
        while(lo < hi){
            int mid = (lo+hi)/2;
            if(r.f <= poses[vind][mid]){
                hi = mid;
            }
            else lo = mid+1;
        }
        works.f = lo;
        lo = 0;
        hi = sz(poses[vind])-1;
        while(lo < hi){
            int mid = (lo+hi)/2+1;
            if(poses[vind][mid] <= r.s){
                lo = mid;
            }
            else hi = mid-1;
        }
        works.s = hi;
        if(works.f > works.s){
            ps(0);
            continue;
        }
        ans = works.s-works.f+1;
        ps(ans);
    }

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 131992 KB Output is correct
2 Correct 78 ms 131868 KB Output is correct
3 Correct 73 ms 131960 KB Output is correct
4 Correct 74 ms 131832 KB Output is correct
5 Correct 73 ms 131832 KB Output is correct
6 Correct 79 ms 131960 KB Output is correct
7 Correct 73 ms 131968 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 264952 KB Output is correct
2 Correct 648 ms 266692 KB Output is correct
3 Correct 805 ms 275592 KB Output is correct
4 Correct 801 ms 276520 KB Output is correct
5 Correct 589 ms 211960 KB Output is correct
6 Correct 606 ms 212344 KB Output is correct
7 Correct 814 ms 288880 KB Output is correct
8 Correct 881 ms 294112 KB Output is correct
9 Correct 877 ms 293880 KB Output is correct
10 Correct 573 ms 232040 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 163316 KB Output is correct
2 Correct 239 ms 153056 KB Output is correct
3 Correct 250 ms 158456 KB Output is correct
4 Correct 244 ms 152696 KB Output is correct
5 Correct 239 ms 153084 KB Output is correct
6 Correct 274 ms 158668 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 131992 KB Output is correct
2 Correct 78 ms 131868 KB Output is correct
3 Correct 73 ms 131960 KB Output is correct
4 Correct 74 ms 131832 KB Output is correct
5 Correct 73 ms 131832 KB Output is correct
6 Correct 79 ms 131960 KB Output is correct
7 Correct 73 ms 131968 KB Output is correct
8 Correct 586 ms 264952 KB Output is correct
9 Correct 648 ms 266692 KB Output is correct
10 Correct 805 ms 275592 KB Output is correct
11 Correct 801 ms 276520 KB Output is correct
12 Correct 589 ms 211960 KB Output is correct
13 Correct 606 ms 212344 KB Output is correct
14 Correct 814 ms 288880 KB Output is correct
15 Correct 881 ms 294112 KB Output is correct
16 Correct 877 ms 293880 KB Output is correct
17 Correct 573 ms 232040 KB Output is correct
18 Correct 299 ms 163316 KB Output is correct
19 Correct 239 ms 153056 KB Output is correct
20 Correct 250 ms 158456 KB Output is correct
21 Correct 244 ms 152696 KB Output is correct
22 Correct 239 ms 153084 KB Output is correct
23 Correct 274 ms 158668 KB Output is correct
24 Correct 777 ms 275508 KB Output is correct
25 Correct 918 ms 284408 KB Output is correct
26 Correct 721 ms 269560 KB Output is correct
27 Correct 739 ms 280424 KB Output is correct
28 Execution timed out 1605 ms 319472 KB Time limit exceeded
29 Halted 0 ms 0 KB -