제출 #267496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
267496		Autoratch	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	372 ms	35064 KiB

selling_rna

#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';
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40