oj.uz

Submission #403565

# Submission time Handle Problem Language Result Execution time Memory
403565 2021-05-13T09:36:52 Z FEDIKUS Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 667 ms 219204 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

const int maxn=1e5+10;
const int maxa=2e6+10;
const int pp=31;
const int mod=1e9+7;
str niz[maxn];
str nizrr[maxn];
pair<str,int> nizr[maxn];
int novi[maxa];
pii kad[maxn];
int koliko=0;
int koji[256];
vector<int> tree[4*maxa+50];

int mul(ll a,ll b){
    if(a*b>=mod) return a*b%mod;
    return a*b;
}

int add(ll a,ll b){
    if(a+b>=mod) return (a+b)%mod;
    return a+b;
}

int sta(int mid,str &p,str *niz){
    if(p.size()>niz[mid].size()){
        return (p<niz[mid] ? 3:1);
    }
    for(int i=0;i<min(p.size(),niz[mid].size());i++){
        if(p[i]<niz[mid][i]) return 3;
        if(p[i]>niz[mid][i]) return 1;
    }
    return 2;
}

pii range(str &p,int n,str *niz){
    int l=0;
    int r=n-1;
    int prvi=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        int odg=sta(mid,p,niz);
        if(odg==1){
            l=mid+1;
        }else if(odg==2){
            r=mid-1;
            prvi=mid;
        }else r=mid-1;
    }

    l=0;
    r=n-1;
    int drugi=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        int odg=sta(mid,p,niz);
        if(odg==1){
            l=mid+1;
        }else if(odg==2){
            l=mid+1;
            drugi=mid;
        }else r=mid-1;
    }
    if(prvi==-1 || drugi==-1) return {-1,-1};
    return {prvi,drugi};
}

void spoji(vector<int> &a,vector<int> &b,vector<int> &res){
    res.resize(a.size()+b.size());
    int tren=0;
    int i=0;
    int j=0;
    while(i<a.size() || j<b.size()){
        res[tren]=INT_MAX;
        if(i<a.size()) res[tren]=min(res[tren],a[i]);
        if(j<b.size()) res[tren]=min(res[tren],b[j]);
        if(i<a.size() && a[i]==res[tren]) i++;
        else if(j<b.size() && b[j]==res[tren]) j++;
        tren++;
    }
}

void build(int ind,int l,int r){
    if(l==r){
        tree[ind]={novi[l]};
        return;
    }
    int mid=l+(r-l)/2;
    build(2*ind,l,mid);
    build(2*ind+1,mid+1,r);
    spoji(tree[2*ind],tree[2*ind+1],tree[ind]);
}

int query(int ind,int l,int r,int tl,int tr,int vl,int vr){
    if(tl<=l && r<=tr){
        return upper_bound(tree[ind].begin(),tree[ind].end(),vr)-lower_bound(tree[ind].begin(),tree[ind].end(),vl);
    }
    int mid=l+(r-l)/2;
    int ret=0;
    if(tl<=mid) ret+=query(2*ind,l,mid,tl,tr,vl,vr);
    if(tr>mid) ret+=query(2*ind+1,mid+1,r,tl,tr,vl,vr);
    return ret;
}

void solve(){
    koji['A']=1;
    koji['G']=2;
    koji['C']=3;
    koji['U']=4;
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>niz[i];
    }
    sort(niz,niz+n);
    for(int i=0;i<n;i++){
        reverse(niz[i].begin(),niz[i].end());
        nizr[i].xx=niz[i];
        nizr[i].yy=i;
        nizrr[i]=niz[i];
        reverse(niz[i].begin(),niz[i].end());
    }
    sort(nizr,nizr+n);
    sort(nizrr,nizrr+n);
    for(int i=0;i<n;i++){
        novi[nizr[i].yy]=i;
    }
    koliko=n;
    build(1,0,koliko-1);
    while(m--){
        str p,q;
        cin>>p>>q;
        pii pom=range(p,n,niz);
        reverse(q.begin(),q.end());
        pii pom2=range(q,n,nizrr);
        if(pom.xx==-1 || pom.yy==-1){cout<<0<<"\n"; continue;}
        /*int res=0;
        for(int i=pom.xx;i<=pom.yy;i++){
            if(novi[i]>=pom2.xx && novi[i]<=pom2.yy)  res++;
        }*/
        //cout<<pom.xx<<" "<<pom.yy<<"\n";
        //cout<<pom2.xx<<" "<<pom2.yy<<"\n";
        cout<<query(1,0,koliko-1,pom.xx,pom.yy,pom2.xx,pom2.yy)<<"\n";
    }
}

int main(){
    ios;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int sta(int, str&, str*)':
selling_rna.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   53 |     for(int i=0;i<min(p.size(),niz[mid].size());i++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void spoji(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
selling_rna.cpp:97:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     while(i<a.size() || j<b.size()){
      |           ~^~~~~~~~~
selling_rna.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     while(i<a.size() || j<b.size()){
      |                         ~^~~~~~~~~
selling_rna.cpp:99:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         if(i<a.size()) res[tren]=min(res[tren],a[i]);
      |            ~^~~~~~~~~
selling_rna.cpp:100:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         if(j<b.size()) res[tren]=min(res[tren],b[j]);
      |            ~^~~~~~~~~
selling_rna.cpp:101:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         if(i<a.size() && a[i]==res[tren]) i++;
      |            ~^~~~~~~~~
selling_rna.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         else if(j<b.size() && b[j]==res[tren]) j++;
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 198468 KB Output is correct
2 Correct 103 ms 198364 KB Output is correct
3 Correct 107 ms 198300 KB Output is correct
4 Correct 103 ms 198340 KB Output is correct
5 Correct 161 ms 198340 KB Output is correct
6 Correct 106 ms 198488 KB Output is correct
7 Correct 104 ms 198264 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 205520 KB Output is correct
2 Correct 177 ms 205960 KB Output is correct
3 Correct 172 ms 205784 KB Output is correct
4 Correct 181 ms 205892 KB Output is correct
5 Correct 134 ms 203696 KB Output is correct
6 Correct 136 ms 203740 KB Output is correct
7 Correct 171 ms 204016 KB Output is correct
8 Correct 192 ms 205764 KB Output is correct
9 Correct 238 ms 205796 KB Output is correct
10 Correct 161 ms 205824 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 204944 KB Output is correct
2 Correct 195 ms 202120 KB Output is correct
3 Correct 218 ms 203528 KB Output is correct
4 Correct 184 ms 202640 KB Output is correct
5 Correct 180 ms 202156 KB Output is correct
6 Correct 204 ms 203416 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 198468 KB Output is correct
2 Correct 103 ms 198364 KB Output is correct
3 Correct 107 ms 198300 KB Output is correct
4 Correct 103 ms 198340 KB Output is correct
5 Correct 161 ms 198340 KB Output is correct
6 Correct 106 ms 198488 KB Output is correct
7 Correct 104 ms 198264 KB Output is correct
8 Correct 155 ms 205520 KB Output is correct
9 Correct 177 ms 205960 KB Output is correct
10 Correct 172 ms 205784 KB Output is correct
11 Correct 181 ms 205892 KB Output is correct
12 Correct 134 ms 203696 KB Output is correct
13 Correct 136 ms 203740 KB Output is correct
14 Correct 171 ms 204016 KB Output is correct
15 Correct 192 ms 205764 KB Output is correct
16 Correct 238 ms 205796 KB Output is correct
17 Correct 161 ms 205824 KB Output is correct
18 Correct 205 ms 204944 KB Output is correct
19 Correct 195 ms 202120 KB Output is correct
20 Correct 218 ms 203528 KB Output is correct
21 Correct 184 ms 202640 KB Output is correct
22 Correct 180 ms 202156 KB Output is correct
23 Correct 204 ms 203416 KB Output is correct
24 Correct 241 ms 206524 KB Output is correct
25 Correct 325 ms 206644 KB Output is correct
26 Correct 221 ms 206488 KB Output is correct
27 Correct 269 ms 206532 KB Output is correct
28 Correct 667 ms 219204 KB Output is correct
29 Correct 450 ms 213868 KB Output is correct