Submission #343148

#	Time	Username	Problem	Language	Result	Execution time	Memory
343148		davesamanij	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	602 ms	51408 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define lc (v<<1)    
#define rc (lc|1)
#define pll pair<string, int>
#define ppll pair<int,pll>
#define fr first
#define sc second
#define low lower_bound
#define upp upper_bound
#define pb push_back
#define endl '\n';
#define mp make_pair
const int mxn = 1e5+10;
//const ll inf = 1e18;
const int mod = 1e9+7;
 
ll gcd(ll a, ll b){return !b?a:gcd(b,a%b);}
     
ll lcm(ll a, ll b){return (a/gcd(a, b))*b;}
 
ll pw(ll x, ll y) {
    ll r = 1;
    while (y) {
        if (y & 1) r = 1LL * r * x % mod;
        x = 1LL * x * x % mod;
        y >>= 1;
    }
    return r;
}

int n, m;
string s[mxn],p[mxn],q[mxn];
ll a[mxn],b[mxn],c[mxn],d[mxn],ys[mxn];
vector <ll> dat[mxn<<1];

ll res(ll c,ll d,ll k){
    return low(dat[k].begin(), dat[k].end(),d)-low(dat[k].begin(), dat[k].end(),c);
}

int main(){
    
    cin >> n >> m;

    vector<pll>v;
    
    for(int i=0; i<n; i++)cin >> s[i];
    for(int i=0; i<m; i++)cin >> p[i] >> q[i];
    
    sort(s,s+n);
    
    for(int i=0; i<m; i++){
        a[i]=low(s,s+n,p[i])-s;
        p[i][p[i].size()-1]++;
        b[i]=low(s,s+n,p[i])-s;
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<s[i].size()/2; j++)
            swap(s[i][j],s[i][s[i].size()-1-j]);
        v.pb(mp(s[i],i));
    }

    sort(v.begin(),v.end());
    
    for(int i=0; i<n; i++)ys[v[i].sc] = i;
    
    for(int i=0; i<n; i++)s[i] = v[i].fr;
    
    for(int i=0; i<m; i++){
        for(int j=0; j<q[i].size()/2; j++)
            swap(q[i][j],q[i][q[i].size()-1-j]);
        c[i]=low(s,s+n,q[i])-s;
        q[i][q[i].size()-1]++;
        d[i]=low(s,s+n,q[i])-s;
    }

    for(int i=0; i<n; i++){
        for(ll x = i+mxn; x; x>>=1){
            dat[x].pb(ys[i]);
        }
    }

    for(int i=0; i<mxn<<1; i++)
        sort(dat[i].begin(),dat[i].end());
    
    for(int i=0; i<m; i++){
        
        ll ans = 0, l = a[i]+mxn, r = b[i]+mxn;

        for(; l<r; l>>=1, r>>=1){
            if(l&1)ans+=res(c[i],d[i],l++);
            if(r&1)ans+=res(c[i],d[i],--r);
        }

        cout << ans << endl;
    }

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int j=0; j<s[i].size()/2; j++)
      |                      ~^~~~~~~~~~~~~~
selling_rna.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j=0; j<q[i].size()/2; j++)
      |                      ~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40