제출 #732246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
732246		Seb	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	366 ms	75160 KiB

selling_rna

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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