제출 #242125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242125		rqi	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	1075 ms	287988 KiB

selling_rna

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40