oj.uz

Submission #267496

# Submission time Handle Problem Language Result Execution time Memory
267496 2020-08-16T04:37:01 Z Autoratch Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 372 ms 35064 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 1;

int n,m,suf[N],ans[N];
pair<string,int> sx[N];
string s[N],t[N];
tuple<string,string,int> q[N];
tuple<int,int,int,int> qe[N];
int fw[N];

void update(int idx,int val){ if(!idx) return; while(idx<N) fw[idx]+=val,idx+=(idx & -idx); }

int read(int idx){ int val = 0; while(idx>0) val+=fw[idx],idx-=(idx & -idx); return val; }

string nxt(string s)
{
    s[s.size()-1]++;
    return s;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> s[i],t[i] = s[i],reverse(t[i].begin(),t[i].end());
    for(int i = 1;i <= m;i++) 
    {
        string a,b;
        cin >> a >> b;
        q[i] = {a,b,i};
    }
    sort(s+1,s+n+1);
    sort(t+1,t+n+1);
    for(int i = 1;i <= n;i++) sx[i] = {s[i],i},reverse(sx[i].first.begin(),sx[i].first.end());
    sort(sx+1,sx+n+1);
    for(int i = 1;i <= n;i++) suf[sx[i].second] = i;
    sort(q+1,q+m+1);
    for(int i = 1;i <= m;i++)
    {
        auto [a,b,x] = q[i];
        auto ix = lower_bound(s+1,s+n+1,a),iy = upper_bound(s+1,s+n+1,nxt(a));
        reverse(b.begin(),b.end());
        auto jx = lower_bound(t+1,t+n+1,b),jy = upper_bound(t+1,t+n+1,nxt(b));
        qe[i] = {ix-s,iy-s,jx-t,jy-t};
    }
//    cout << endl;
  //  for(int i = 1;i <= n;i++) cout << i << ' ' << s[i] << endl;
   // cout << endl;
    //for(int i = 1;i <= n;i++) cout << i << ' ' << t[i] << endl;
    //cout << endl;
    for(int i = 1;i <= m;i++)
    {
        auto [s,t,x] = q[i];
        auto [a,b,c,d] = qe[i];
//        cout << s << ' ' << t << ' ' << x << endl;
//        cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
    }
  //  cout << endl;
    int l = 0,r = 1;
    for(int i = 1;i <= m;i++) 
    {
        auto [a,b,c,d] = qe[i];
    //    cout << l << ' ' << r << endl;
      //  cout << a << ' ' << b << ' ' << c << ' '  << d << endl;
        while(r>=b) update(suf[--r],-1);
        while(r<b) update(suf[r++],1);
        while(l<a) update(suf[l++],-1);
        //for(int j = 1;j <= n;j++) cout << read(j)-read(j-1) << ' ';
        //cout << endl;
        ans[get<2>(q[i])] = read(d-1)-read(c-1);
    }
    for(int i = 1;i <= m;i++) cout << ans[i] << '\n';
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         auto [a,b,x] = q[i];
      |              ^
selling_rna.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |         auto [s,t,x] = q[i];
      |              ^
selling_rna.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         auto [a,b,c,d] = qe[i];
      |              ^
selling_rna.cpp:57:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   57 |         auto [a,b,c,d] = qe[i];
      |              ^~~~~~~~~
selling_rna.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |         auto [a,b,c,d] = qe[i];
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17536 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Correct 11 ms 17536 KB Output is correct
4 Correct 11 ms 17536 KB Output is correct
5 Correct 12 ms 17664 KB Output is correct
6 Correct 12 ms 17536 KB Output is correct
7 Correct 13 ms 17536 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 26616 KB Output is correct
2 Correct 60 ms 29816 KB Output is correct
3 Correct 58 ms 29816 KB Output is correct
4 Correct 68 ms 29816 KB Output is correct
5 Correct 57 ms 25464 KB Output is correct
6 Correct 60 ms 25592 KB Output is correct
7 Correct 62 ms 31736 KB Output is correct
8 Correct 79 ms 33784 KB Output is correct
9 Correct 68 ms 33864 KB Output is correct
10 Correct 50 ms 29048 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 19704 KB Output is correct
2 Correct 79 ms 18936 KB Output is correct
3 Correct 97 ms 19320 KB Output is correct
4 Correct 81 ms 19064 KB Output is correct
5 Correct 81 ms 18936 KB Output is correct
6 Correct 93 ms 19296 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17536 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Correct 11 ms 17536 KB Output is correct
4 Correct 11 ms 17536 KB Output is correct
5 Correct 12 ms 17664 KB Output is correct
6 Correct 12 ms 17536 KB Output is correct
7 Correct 13 ms 17536 KB Output is correct
8 Correct 46 ms 26616 KB Output is correct
9 Correct 60 ms 29816 KB Output is correct
10 Correct 58 ms 29816 KB Output is correct
11 Correct 68 ms 29816 KB Output is correct
12 Correct 57 ms 25464 KB Output is correct
13 Correct 60 ms 25592 KB Output is correct
14 Correct 62 ms 31736 KB Output is correct
15 Correct 79 ms 33784 KB Output is correct
16 Correct 68 ms 33864 KB Output is correct
17 Correct 50 ms 29048 KB Output is correct
18 Correct 114 ms 19704 KB Output is correct
19 Correct 79 ms 18936 KB Output is correct
20 Correct 97 ms 19320 KB Output is correct
21 Correct 81 ms 19064 KB Output is correct
22 Correct 81 ms 18936 KB Output is correct
23 Correct 93 ms 19296 KB Output is correct
24 Correct 104 ms 30636 KB Output is correct
25 Correct 159 ms 31736 KB Output is correct
26 Correct 93 ms 30384 KB Output is correct
27 Correct 104 ms 30712 KB Output is correct
28 Correct 372 ms 35064 KB Output is correct
29 Correct 286 ms 24056 KB Output is correct