oj.uz

Submission #242118

# Submission time Handle Problem Language Result Execution time Memory
242118 2020-06-26T21:34:19 Z rqi Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 314228 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];

double inittime = 0;

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;
        clock_t x = clock();
        csum[0] = csum[1] = pows[0] = pows[1] = ipows[0] = ipows[1] = vi(n+1, 0);
        inittime+=double(double(clock())-x)/CLOCKS_PER_SEC;
        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 75 ms 131960 KB Output is correct
2 Correct 75 ms 131960 KB Output is correct
3 Correct 76 ms 131960 KB Output is correct
4 Correct 75 ms 131960 KB Output is correct
5 Correct 79 ms 132088 KB Output is correct
6 Correct 75 ms 131960 KB Output is correct
7 Correct 79 ms 131960 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 260320 KB Output is correct
2 Correct 415 ms 261752 KB Output is correct
3 Correct 540 ms 270456 KB Output is correct
4 Correct 566 ms 271608 KB Output is correct
5 Correct 351 ms 209272 KB Output is correct
6 Correct 359 ms 209656 KB Output is correct
7 Correct 546 ms 283128 KB Output is correct
8 Correct 515 ms 289400 KB Output is correct
9 Correct 497 ms 289784 KB Output is correct
10 Correct 395 ms 227832 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 163088 KB Output is correct
2 Correct 299 ms 152952 KB Output is correct
3 Correct 349 ms 158200 KB Output is correct
4 Correct 324 ms 152568 KB Output is correct
5 Correct 321 ms 152824 KB Output is correct
6 Correct 374 ms 158212 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 131960 KB Output is correct
2 Correct 75 ms 131960 KB Output is correct
3 Correct 76 ms 131960 KB Output is correct
4 Correct 75 ms 131960 KB Output is correct
5 Correct 79 ms 132088 KB Output is correct
6 Correct 75 ms 131960 KB Output is correct
7 Correct 79 ms 131960 KB Output is correct
8 Correct 365 ms 260320 KB Output is correct
9 Correct 415 ms 261752 KB Output is correct
10 Correct 540 ms 270456 KB Output is correct
11 Correct 566 ms 271608 KB Output is correct
12 Correct 351 ms 209272 KB Output is correct
13 Correct 359 ms 209656 KB Output is correct
14 Correct 546 ms 283128 KB Output is correct
15 Correct 515 ms 289400 KB Output is correct
16 Correct 497 ms 289784 KB Output is correct
17 Correct 395 ms 227832 KB Output is correct
18 Correct 429 ms 163088 KB Output is correct
19 Correct 299 ms 152952 KB Output is correct
20 Correct 349 ms 158200 KB Output is correct
21 Correct 324 ms 152568 KB Output is correct
22 Correct 321 ms 152824 KB Output is correct
23 Correct 374 ms 158212 KB Output is correct
24 Correct 585 ms 270244 KB Output is correct
25 Correct 760 ms 278904 KB Output is correct
26 Correct 524 ms 264132 KB Output is correct
27 Correct 595 ms 275192 KB Output is correct
28 Execution timed out 1612 ms 314228 KB Time limit exceeded
29 Halted 0 ms 0 KB -