oj.uz

Submission #242125

# Submission time Handle Problem Language Result Execution time Memory
242125 2020-06-26T22:38:13 Z rqi Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1075 ms 287988 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){
    return S[a] < S[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 66 ms 113152 KB Output is correct
2 Correct 65 ms 113144 KB Output is correct
3 Correct 64 ms 113144 KB Output is correct
4 Correct 66 ms 113148 KB Output is correct
5 Correct 65 ms 113376 KB Output is correct
6 Correct 65 ms 113144 KB Output is correct
7 Correct 66 ms 113144 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 236920 KB Output is correct
2 Correct 373 ms 238456 KB Output is correct
3 Correct 533 ms 247032 KB Output is correct
4 Correct 573 ms 248204 KB Output is correct
5 Correct 334 ms 187588 KB Output is correct
6 Correct 327 ms 187768 KB Output is correct
7 Correct 468 ms 258936 KB Output is correct
8 Correct 460 ms 264280 KB Output is correct
9 Correct 473 ms 266104 KB Output is correct
10 Correct 352 ms 205176 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 144124 KB Output is correct
2 Correct 176 ms 133880 KB Output is correct
3 Correct 205 ms 139336 KB Output is correct
4 Correct 179 ms 133756 KB Output is correct
5 Correct 190 ms 133880 KB Output is correct
6 Correct 207 ms 139256 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 113152 KB Output is correct
2 Correct 65 ms 113144 KB Output is correct
3 Correct 64 ms 113144 KB Output is correct
4 Correct 66 ms 113148 KB Output is correct
5 Correct 65 ms 113376 KB Output is correct
6 Correct 65 ms 113144 KB Output is correct
7 Correct 66 ms 113144 KB Output is correct
8 Correct 351 ms 236920 KB Output is correct
9 Correct 373 ms 238456 KB Output is correct
10 Correct 533 ms 247032 KB Output is correct
11 Correct 573 ms 248204 KB Output is correct
12 Correct 334 ms 187588 KB Output is correct
13 Correct 327 ms 187768 KB Output is correct
14 Correct 468 ms 258936 KB Output is correct
15 Correct 460 ms 264280 KB Output is correct
16 Correct 473 ms 266104 KB Output is correct
17 Correct 352 ms 205176 KB Output is correct
18 Correct 212 ms 144124 KB Output is correct
19 Correct 176 ms 133880 KB Output is correct
20 Correct 205 ms 139336 KB Output is correct
21 Correct 179 ms 133756 KB Output is correct
22 Correct 190 ms 133880 KB Output is correct
23 Correct 207 ms 139256 KB Output is correct
24 Correct 489 ms 246336 KB Output is correct
25 Correct 650 ms 254840 KB Output is correct
26 Correct 442 ms 240760 KB Output is correct
27 Correct 522 ms 251640 KB Output is correct
28 Correct 1075 ms 287988 KB Output is correct
29 Correct 755 ms 231156 KB Output is correct