Submission #365422

#	Time	Username	Problem	Language	Result	Execution time	Memory
365422		BartolM	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	301 ms	167088 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <pii, pii> ppp;

const int INF=0x3f3f3f3f;
const int N=1e5+5;
const int MAX=2e6+5;

struct Node{
    Node* CH[4];
    int dt, kraj, rig;
    Node() {
        dt=0; kraj=0;
        memset(CH, 0, sizeof CH);
    }
};

int n, q, len, cnt=0;
char inp[N];
string s[N];

Node *root=new Node(), *root_r=new Node();

int sol[N];
vector <int> toc[N];
vector <ppp> v[N]; //((dole, gore), (index, +-1))
int F[N];

void update(int x, int val) {
    for (x++; x<=n+1; x+=x&-x) F[x]+=val;
}

int query_(int x) {
    int ret=0;
    for (x++; x>0; x-=x&-x) ret+=F[x];
    return ret;
}

int query(int l, int r) {
    return query_(r-1)-query_(l-1);
}

void dodaj(Node *curr) {
    for (int i=0; i<len; ++i) {
        if (curr->CH[inp[i]-'A']==NULL) curr->CH[inp[i]-'A']=new Node();
        curr=curr->CH[inp[i]-'A'];
    }
    curr->kraj=1;
}

void dfs(Node *curr) {
    if (!curr) return;
    curr->dt=cnt;
    cnt+=curr->kraj;
    for (int i=0; i<4; ++i) dfs(curr->CH[i]);
    curr->rig=cnt;
}

pii interval(Node* curr) {
    len=strlen(inp);
    for (int i=0; i<len; ++i) {
        curr=curr->CH[inp[i]-'A'];
        if (!curr) return mp(0, 0);
    }
    return mp(curr->dt, curr->rig);
}

void convert() {
    for (int i=0; i<len; ++i) {
        if (inp[i]=='G') inp[i]='B';
        if (inp[i]=='U') inp[i]='D';
    }
}

void solve() {
    dfs(root);
    cnt=0;
    dfs(root_r);
    for (int i=0; i<q; ++i) {
        scanf("%s", inp);
        len=strlen(inp);
        convert();
        pii a=interval(root);

        scanf("%s", inp); len=strlen(inp);
        reverse(inp, inp+len);
        convert();
        pii b=interval(root_r);

        v[a.X].pb({b, {i, -1}});
        v[a.Y].pb({b, {i, 1}});
    }
    for (int i=0; i<n; ++i) {
        len=s[i].size();
        for (int j=0; j<len; ++j) inp[j]=s[i][j];
        inp[len]='\0';
//        printf("string: %s\n", inp);

        int x=interval(root).X;
        reverse(inp, inp+len);
        int y=interval(root_r).X;
        toc[x].pb(y);
    }

    for (int i=0; i<=n+1; ++i) {
        for (ppp pp:v[i]) sol[pp.Y.X]+=pp.Y.Y*query(pp.X.X, pp.X.Y);
        for (int y:toc[i]) update(y, 1);
    }

    for (int i=0; i<q; ++i) printf("%d\n", sol[i]);
}

void load() {
    scanf("%d %d", &n, &q);
    for (int i=0; i<n; ++i) {
        scanf("%s", inp);

        len=strlen(inp);
        convert();
        s[i]=inp;

        dodaj(root);
        reverse(inp, inp+len);
        dodaj(root_r);
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |         scanf("%s", inp);
      |         ~~~~~^~~~~~~~~~~
selling_rna.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |         scanf("%s", inp); len=strlen(inp);
      |         ~~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void load()':
selling_rna.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |         scanf("%s", inp);
      |         ~~~~~^~~~~~~~~~~

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