Submission #44778

#	Time	Username	Problem	Language	Result	Execution time	Memory
44778		PowerOfNinjaGo	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	740 ms	77200 KiB

selling_rna

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
typedef pair<string, int> psi;
int n, q;
vector<string> vec;
vector< psi > suf;
vector<string> prefix;
vector<string> suffix;
const int maxlen = 2e6+5;
char tmp[maxlen];
bool cmp(psi a, psi b)
{
    reverse(a.X.begin(), a.X.end());
    reverse(b.X.begin(), b.X.end());
    return a.X< b.X;
}
struct node
{
    int v;
    node *left, *right;
    node(int a, node *b, node *c)
    {
        v = a;
        left = b; right = c;
    }
    node* insert(int dat, int L = 1, int R = n)
    {
        if(L<= dat && dat<= R)
        {
            if(L == R) return new node(v+1, NULL, NULL);
            int M = (L+R)/2;
            return new node(v+1, left->insert(dat, L, M), right->insert(dat, M+1, R));
        }
        return this;
    }
    int ask(int i, int j, int p = 1, int L = 1, int R = n)
    {
        if(i> R || j< L) return 0;
        if(i<= L && R<= j) return v;
        int M = (L+R)/2;
        int x = left->ask(i, j, 2*p, L, M);
        int y = right->ask(i, j, 2*p+1, M+1, R);
        return x+y;
    }
};
node *zero = new node(0, NULL, NULL);
node* root[maxlen];
int match(vector<string> &yo, int ind, string &x)
{
    for(int i = 0; i< (int) x.size() && i< (int) yo[ind].size(); i++)
        if(yo[ind][i] != x[i]) return i;
    return min(x.size(), yo[ind].size());
}
ii findra(vector<string> &yo, string &x)
{
    //find first to >=
    int lo = 1, hi = n;
    int k = x.size();
    while(lo< hi)
    {
        int mid = (lo+hi)/2;
        if(yo[mid]> x and match(yo, mid, x) == k) hi = mid;
        else if(yo[mid] >= x) hi = mid;
        else lo = mid+1;
    }
    int lend = lo;
    // printf("lend is %d for %s\n", lend, x.c_str());
    if(match(yo, lend, x) != k) return ii(-1, -1);
    lo = 1, hi = n;
    //find last to <=
    while(lo< hi)
    {
        int mid = (lo+hi+1)/2;
        // printf("match %d is %d\n", mid, match(yo, mid, x));
        if(yo[mid]> x and match(yo, mid, x) == k) lo = mid;
        else if(yo[mid]> x) hi = mid-1;
        else lo = mid;
    }
    return ii(lend, lo);
}
int main()
{
    zero = new node(0, NULL, NULL);
    zero->left = zero->right = zero;
    scanf("%d %d", &n, &q);
    vec.pb("@");
    for(int i = 1; i<= n; i++)
    {
        scanf("%s", tmp);
        vec.pb(string(tmp));
    }
    sort(vec.begin(), vec.end());
    for(int i = 1; i<= n; i++)
    {
        suf.pb(make_pair(vec[i], i));
        reverse(suf.back().X.begin(), suf.back().X.end());
    }
    suf.pb(make_pair("@", 0));
    sort(suf.begin(), suf.end());
    // for(int i = 1; i<= n; i++) printf("%d: %s\n", i, vec[i].c_str());
    // for(int i = 1; i<= n ;i++) printf("%d: %s\n", i, suf[i].X.c_str());
    for(int i = 1; i<= n; i++)
    {
        // printf("%d ", suf[i].Y);
        root[i] = (i> 1?root[i-1]:zero)->insert(suf[i].Y);
    }
    // printf("\n");
    swap(prefix, vec);
    for(int i = 0; i<= n; i++) suffix.pb(suf[i].X);
    while(q--)
    {
        string prf, sf;
        scanf("%s", tmp);
        prf = string(tmp);
        scanf("%s", tmp);
        sf = string(tmp);
        reverse(sf.begin(), sf.end());
        auto res = findra(prefix, prf);
        auto res2 = findra(suffix, sf);
        if(res.X == -1 or res2.Y == -1)
        {
            puts("0");
            continue;
        }
        int x1 = res.X, x2 = res.Y;
        int y1 = res2.X, y2 = res2.Y;
        // printf("(%d, %d)\n", x1, x2);
        // printf("(%d, %d)\n", y1, y2);
        int ret = root[y2]->ask(x1, x2)-(y1>1?root[y1-1]->ask(x1, x2):0);
        ret = max(ret, 0);
        printf("%d\n", ret);
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", tmp);
         ~~~~~^~~~~~~~~~~
selling_rna.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", tmp);
         ~~~~~^~~~~~~~~~~
selling_rna.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", tmp);
         ~~~~~^~~~~~~~~~~

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