oj.uz

Submission #242119

# Submission time Handle Problem Language Result Execution time Memory
242119 2020-06-26T21:37:03 Z rqi Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1305 ms 288116 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;
    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;
unordered_set<ll> us;
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";
}

clock_t c;
int cur = 0;
void w(){ 
    cout << "B" << ++cur << " " << double(clock()-c)/CLOCKS_PER_SEC << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    //w();
    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]);
    }
    //w();
    for(int i = 1; i <= M; i++){
        cin >> P[i] >> Q[i];
        Phash[i].init(P[i]);
        Qhash[i].init(Q[i]);
    }
    //w();

    //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);
    //w();
    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
    }
    //w();
    //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;
    }
    //w();
    //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)];
        us.ins(Qhash[i].hash(0, sz(Q[i])-1));
    }
    //w();
    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(us.count(Shash[i].hash(j, sz(S[i])-1))){
                poses[m[Shash[i].hash(j, sz(S[i])-1)]].pb(i);
            }
        }
    }
    //w();
    //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);
    }
    //w();
    //cout << inittime << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 113144 KB Output is correct
2 Correct 64 ms 113144 KB Output is correct
3 Correct 64 ms 113144 KB Output is correct
4 Correct 63 ms 113144 KB Output is correct
5 Correct 64 ms 113144 KB Output is correct
6 Correct 65 ms 113144 KB Output is correct
7 Correct 63 ms 113144 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 236924 KB Output is correct
2 Correct 388 ms 238328 KB Output is correct
3 Correct 547 ms 247160 KB Output is correct
4 Correct 580 ms 248312 KB Output is correct
5 Correct 332 ms 187512 KB Output is correct
6 Correct 345 ms 187896 KB Output is correct
7 Correct 495 ms 258940 KB Output is correct
8 Correct 484 ms 264312 KB Output is correct
9 Correct 472 ms 265976 KB Output is correct
10 Correct 372 ms 205188 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 144120 KB Output is correct
2 Correct 201 ms 133884 KB Output is correct
3 Correct 207 ms 139256 KB Output is correct
4 Correct 199 ms 133624 KB Output is correct
5 Correct 195 ms 134008 KB Output is correct
6 Correct 221 ms 139256 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 113144 KB Output is correct
2 Correct 64 ms 113144 KB Output is correct
3 Correct 64 ms 113144 KB Output is correct
4 Correct 63 ms 113144 KB Output is correct
5 Correct 64 ms 113144 KB Output is correct
6 Correct 65 ms 113144 KB Output is correct
7 Correct 63 ms 113144 KB Output is correct
8 Correct 373 ms 236924 KB Output is correct
9 Correct 388 ms 238328 KB Output is correct
10 Correct 547 ms 247160 KB Output is correct
11 Correct 580 ms 248312 KB Output is correct
12 Correct 332 ms 187512 KB Output is correct
13 Correct 345 ms 187896 KB Output is correct
14 Correct 495 ms 258940 KB Output is correct
15 Correct 484 ms 264312 KB Output is correct
16 Correct 472 ms 265976 KB Output is correct
17 Correct 372 ms 205188 KB Output is correct
18 Correct 253 ms 144120 KB Output is correct
19 Correct 201 ms 133884 KB Output is correct
20 Correct 207 ms 139256 KB Output is correct
21 Correct 199 ms 133624 KB Output is correct
22 Correct 195 ms 134008 KB Output is correct
23 Correct 221 ms 139256 KB Output is correct
24 Correct 524 ms 246240 KB Output is correct
25 Correct 648 ms 254712 KB Output is correct
26 Correct 461 ms 240632 KB Output is correct
27 Correct 532 ms 251512 KB Output is correct
28 Correct 1305 ms 288116 KB Output is correct
29 Correct 1012 ms 234376 KB Output is correct