oj.uz

Submission #343148

# Submission time Handle Problem Language Result Execution time Memory
343148 2021-01-03T12:50:33 Z davesamanij Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 602 ms 51408 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14444 KB Output is correct
2 Correct 9 ms 14444 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 9 ms 14444 KB Output is correct
5 Correct 9 ms 14444 KB Output is correct
6 Correct 9 ms 14444 KB Output is correct
7 Correct 9 ms 14444 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 23916 KB Output is correct
2 Correct 142 ms 24648 KB Output is correct
3 Correct 134 ms 24300 KB Output is correct
4 Correct 135 ms 24648 KB Output is correct
5 Correct 94 ms 21192 KB Output is correct
6 Correct 97 ms 21320 KB Output is correct
7 Correct 158 ms 24300 KB Output is correct
8 Correct 181 ms 25032 KB Output is correct
9 Correct 178 ms 25032 KB Output is correct
10 Correct 117 ms 22472 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 27484 KB Output is correct
2 Correct 105 ms 22112 KB Output is correct
3 Correct 138 ms 24796 KB Output is correct
4 Correct 107 ms 23132 KB Output is correct
5 Correct 97 ms 22112 KB Output is correct
6 Correct 122 ms 24796 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14444 KB Output is correct
2 Correct 9 ms 14444 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 9 ms 14444 KB Output is correct
5 Correct 9 ms 14444 KB Output is correct
6 Correct 9 ms 14444 KB Output is correct
7 Correct 9 ms 14444 KB Output is correct
8 Correct 116 ms 23916 KB Output is correct
9 Correct 142 ms 24648 KB Output is correct
10 Correct 134 ms 24300 KB Output is correct
11 Correct 135 ms 24648 KB Output is correct
12 Correct 94 ms 21192 KB Output is correct
13 Correct 97 ms 21320 KB Output is correct
14 Correct 158 ms 24300 KB Output is correct
15 Correct 181 ms 25032 KB Output is correct
16 Correct 178 ms 25032 KB Output is correct
17 Correct 117 ms 22472 KB Output is correct
18 Correct 154 ms 27484 KB Output is correct
19 Correct 105 ms 22112 KB Output is correct
20 Correct 138 ms 24796 KB Output is correct
21 Correct 107 ms 23132 KB Output is correct
22 Correct 97 ms 22112 KB Output is correct
23 Correct 122 ms 24796 KB Output is correct
24 Correct 189 ms 26756 KB Output is correct
25 Correct 270 ms 28036 KB Output is correct
26 Correct 162 ms 26116 KB Output is correct
27 Correct 181 ms 26756 KB Output is correct
28 Correct 602 ms 51408 KB Output is correct
29 Correct 425 ms 40812 KB Output is correct