Submission #515739

#	Time	Username	Problem	Language	Result	Execution time	Memory
515739		Killer2501	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	262 ms	147348 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const int M = 450;
const ll inf = 1e15;
const ll mod = 1e9+7;
const ll mod1 = 1e9+3;
const int base = 311;
const int base1 = 97;
int n, k, m, lab[N], a[N], b[N], c[N], d[N], t, cnt;
ll ans, tong;
string s[N];
struct node
{
    int x[4];
    vector<int> val;
    node(){}
    node(int t)
    {
        memset(x, t, sizeof(x));
    }
};
char ch[4] = {'A', 'U', 'G', 'C'};
vector<node> q;
void add(int id)
{
    int i = 0;
    for(int j = 0; j < (int)s[id].length(); j ++)
    {
        int k = 0;
        for(int p = 0; p < 4; p ++)
        {
            if(ch[p] == s[id][j])
            {
                k = p;
                break;
            }
        }
        if(q[i].x[k] == 0)
        {
            q[i].x[k] = q.size();
            q.pb(node(0));
        }
        i = q[i].x[k];
        q[i].val.pb(id);
    }

}
int get(string s, int l, int r)
{
    if(l > r)return 0;
    int i = 0;
    for(int j = 0; j < (int)s.length(); j ++)
    {
        int k = 0;
        for(int p = 0; p < 4; p ++)
        {
            if(ch[p] == s[j])
            {
                k = p;
                break;
            }
        }
        if(q[i].x[k] == 0)return 0;
        i = q[i].x[k];
    }
    return upper_bound(q[i].val.begin(), q[i].val.end(), r) - lower_bound(q[i].val.begin(), q[i].val.end(), l);
}
struct IT
{
    int n;
    vector<int> st, lazy;
    IT(int _n)
    {
        n = _n;
        st.resize(n*4+4, 0);
        lazy.resize(n*4+4, 0);
    }
    void down(int id, int l, int r, int mid)
    {
        if(lazy[id] == 0)return;
        st[id<<1] = (mid-l+1) - st[id<<1];
        st[id<<1|1] = (r-mid) - st[id<<1|1];
        lazy[id<<1] ^= lazy[id];
        lazy[id<<1|1] ^= lazy[id];
        lazy[id] = 0;
    }
    void update(int id, int l, int r, int u, int v)
    {
        if(u <= l && r <= v)
        {
            st[id] = (r-l+1) - st[id];
            lazy[id] ^= 1;
        }
        if(u > r || l > v)return;
        int mid = (l+r)>>1;
        down(id, l, r, mid);
        update(id<<1, l, mid, u, v);
        update(id<<1|1, mid+1, r, u, v);
        st[id] = st[id<<1]+st[id<<1|1];
    }
    void update(int l, int r)
    {
        update(1, 1, n, l, r);
    }
    int get(int id, int l, int r, int u, int v)
    {
        if(u <= l && r <= v)return st[id];
        if(u > r || l > v)return 0;
        int mid = (l+r)>>1;
        down(id, l, r, mid);
        return get(id<<1, l, mid, u, v) + get(id<<1|1, mid+1, r, u, v);
    }
    int get(int l, int r)
    {
        return get(1, 1, n, l ,r);
    }
};
vector<int> vi;
bool strmin(string x, string y)
{
    for(int i = 0; i < (int)min(x.length(), y.length()); i ++)
    {
        if(x[i] < y[i])return true;
        if(x[i] > y[i])return false;
    }
    if(x.length() >= y.length())return false;
    return true;
}
bool strmax(string x, string y)
{
    for(int i = 0; i < (int)min(x.length(), y.length()); i ++)
    {
        if(x[i] > y[i])return true;
        if(x[i] < y[i])return false;
    }
    if(x.length() >= y.length())return false;
    return true;
}
void sol()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)cin >> s[i];
    sort(s+1, s+1+n);
    q.pb(node(0));
    for(int i = 1; i <= n; i ++)
    {
        //cout << s[i] << '\n';
        reverse(s[i].begin(), s[i].end());
        add(i);
        reverse(s[i].begin(), s[i].end());
    }
    while(m -- > 0)
    {
        string pre, suf;
        cin >> pre >> suf;
        reverse(suf.begin(), suf.end());
        int l = 1, r = n, mid;
        while(l <= r)
        {
            mid = (l+r)>>1;
            if(strmax(s[mid], pre))r = mid-1;
            else l = mid+1;
        }
        k = r;
        l = 1;
        while(l <= r)
        {
            mid = (l+r)>>1;
            if(strmin(s[mid], pre))l = mid+1;
            else r = mid-1;
        }
        r = k;
        //cout << l <<" "<<r<<'\n';
        cout << get(suf, l, r) << '\n';
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*

*/

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:194:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:195:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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