oj.uz

Submission #267325

# Submission time Handle Problem Language Result Execution time Memory
267325 2020-08-16T03:51:02 Z Autoratch Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 113 ms 29608 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};
    }
    int l = 0,r = 1;
    for(int i = 1;i <= m;i++) 
    {
        auto [a,b,c,d] = qe[i];
        while(r<=b) update(r++,1);
        while(l<a) update(l++,-1);
        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:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         auto [a,b,c,d] = qe[i];
      |              ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 17536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 29608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 19576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 17536 KB Output isn't correct
2 Halted 0 ms 0 KB -