oj.uz

Submission #732246

# Submission time Handle Problem Language Result Execution time Memory
732246 2023-04-28T19:37:59 Z Seb Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 366 ms 75160 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define f first
#define s second

const ll MAXN = 1e5+5;

string s[MAXN];
pair <string,ll> r[MAXN];
ll ar[MAXN];

struct wavelet {
    wavelet *l, *r;
    ll ini,fin;
    vector <ll> v,in;
    wavelet (ll INI, ll FIN) {
        ini = INI;
        fin = FIN;
    }
    void setup(ll num[]) {
        if (ini==fin) return;
        l = new wavelet(ini,(ini+fin)/2);
        r = new wavelet((ini+fin)/2+1,fin);
        for (int i=0;i<in.size();i++) {
            if (num[in[i]]<=(ini+fin)/2) {
                if (!v.empty()) v.push_back(v[v.size()-1]+1);
                else v.push_back(1);
                l->in.push_back(in[i]);
            }
            else {
                if (!v.empty()) v.push_back(v[v.size()-1]);
                else v.push_back(0);
                r->in.push_back(in[i]);
            }
        }
        l->setup(num);
        r->setup(num);
        return;
    }
    ll query(ll L, ll R, ll a, ll b) {
        if (ini>b || a>fin || R<L) return 0;
        if (a<=ini && fin<=b) return R-L+1;
        ll aux = 0;
        if (L>0) aux += l->query(v[L-1],v[R]-1,a,b);
        else aux += l->query(0,v[R]-1,a,b);
        if (L>0) aux += r->query(L-v[L-1],R-v[R],a,b);
        else aux += r->query(L,R-v[R],a,b);
        return aux;
    }
};

ll bin_pre1(ll ini, ll fin, string &pre) { //devuelve el primero igual o mayor
    if (ini==fin) return ini;
    if (pre>s[(ini+fin)/2]) return bin_pre1((ini+fin)/2+1,fin,pre);
    else return bin_pre1(ini,(ini+fin)/2,pre);
}

ll bin_pre2(ll ini, ll fin, string &pre) { //devuelve el primero mas grande
    if (ini==fin) return ini;
    if (pre>=(s[(ini+fin)/2].substr(0,pre.size()))) return bin_pre2((ini+fin)/2+1,fin,pre);
    else return bin_pre2(ini,(ini+fin)/2,pre);
}

ll bin_suf1(ll ini, ll fin, string &pre) { //devuelve el primero igual o mayor
    if (ini==fin) return ini;
    if (pre>r[(ini+fin)/2].f) return bin_suf1((ini+fin)/2+1,fin,pre);
    else return bin_suf1(ini,(ini+fin)/2,pre);
}

ll bin_suf2(ll ini, ll fin, string &pre) { //devuelve el primero mas grande
    if (ini==fin) return ini;
    if (pre>=(r[(ini+fin)/2].f.substr(0,pre.size()))) return bin_suf2((ini+fin)/2+1,fin,pre);
    else return bin_suf2(ini,(ini+fin)/2,pre);
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,q,a,b,c,d;
string pre,suf;
cin>>n>>q;
for (int i=0;i<n;i++) cin>>s[i];
sort(s,s+n);
for (int i=0;i<n;i++) {
    r[i].f = s[i];
    reverse(r[i].f.begin(),r[i].f.end());
    r[i].s = i;
}
sort(r,r+n);
for (int i=0;i<n;i++) ar[r[i].s] = i;
wavelet *wave = new wavelet(0,MAXN);
for (int i=0;i<n;i++) wave->in.push_back(i);
wave->setup(ar);
while (q--) {
    cin>>pre>>suf;
    reverse(suf.begin(),suf.end());
    a = bin_suf1(0,n,suf);
    b = bin_suf2(0,n,suf)-1;
    c = bin_pre1(0,n,pre);
    d = bin_pre2(0,n,pre)-1;
    cout<<wave->query(c,d,a,b)<<'\n';
}
return 0;
}

Compilation message

selling_rna.cpp: In member function 'void wavelet::setup(ll*)':
selling_rna.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i=0;i<in.size();i++) {
      |                      ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 26128 KB Output is correct
2 Correct 16 ms 26192 KB Output is correct
3 Correct 18 ms 26196 KB Output is correct
4 Correct 16 ms 26188 KB Output is correct
5 Correct 16 ms 26196 KB Output is correct
6 Correct 16 ms 26148 KB Output is correct
7 Correct 17 ms 26092 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 34892 KB Output is correct
2 Correct 46 ms 36088 KB Output is correct
3 Correct 46 ms 35484 KB Output is correct
4 Correct 48 ms 36100 KB Output is correct
5 Correct 44 ms 33100 KB Output is correct
6 Correct 44 ms 33248 KB Output is correct
7 Correct 45 ms 35268 KB Output is correct
8 Correct 64 ms 37960 KB Output is correct
9 Correct 55 ms 37984 KB Output is correct
10 Correct 55 ms 35488 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 46500 KB Output is correct
2 Correct 93 ms 38268 KB Output is correct
3 Correct 116 ms 42452 KB Output is correct
4 Correct 109 ms 40136 KB Output is correct
5 Correct 88 ms 38236 KB Output is correct
6 Correct 110 ms 42412 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 26128 KB Output is correct
2 Correct 16 ms 26192 KB Output is correct
3 Correct 18 ms 26196 KB Output is correct
4 Correct 16 ms 26188 KB Output is correct
5 Correct 16 ms 26196 KB Output is correct
6 Correct 16 ms 26148 KB Output is correct
7 Correct 17 ms 26092 KB Output is correct
8 Correct 43 ms 34892 KB Output is correct
9 Correct 46 ms 36088 KB Output is correct
10 Correct 46 ms 35484 KB Output is correct
11 Correct 48 ms 36100 KB Output is correct
12 Correct 44 ms 33100 KB Output is correct
13 Correct 44 ms 33248 KB Output is correct
14 Correct 45 ms 35268 KB Output is correct
15 Correct 64 ms 37960 KB Output is correct
16 Correct 55 ms 37984 KB Output is correct
17 Correct 55 ms 35488 KB Output is correct
18 Correct 134 ms 46500 KB Output is correct
19 Correct 93 ms 38268 KB Output is correct
20 Correct 116 ms 42452 KB Output is correct
21 Correct 109 ms 40136 KB Output is correct
22 Correct 88 ms 38236 KB Output is correct
23 Correct 110 ms 42412 KB Output is correct
24 Correct 94 ms 38228 KB Output is correct
25 Correct 182 ms 38480 KB Output is correct
26 Correct 76 ms 38228 KB Output is correct
27 Correct 101 ms 38240 KB Output is correct
28 Correct 366 ms 75160 KB Output is correct
29 Correct 361 ms 69064 KB Output is correct