oj.uz

Submission #365422

# Submission time Handle Problem Language Result Execution time Memory
365422 2021-02-11T16:01:03 Z BartolM Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 301 ms 167088 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 133964 KB Output is correct
2 Correct 254 ms 131364 KB Output is correct
3 Correct 243 ms 136172 KB Output is correct
4 Correct 240 ms 130284 KB Output is correct
5 Correct 295 ms 164716 KB Output is correct
6 Correct 301 ms 167088 KB Output is correct
7 Correct 81 ms 15596 KB Output is correct
8 Correct 238 ms 106092 KB Output is correct
9 Correct 222 ms 91372 KB Output is correct
10 Correct 168 ms 86764 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 10788 KB Output is correct
2 Correct 26 ms 10856 KB Output is correct
3 Correct 31 ms 10656 KB Output is correct
4 Correct 25 ms 10184 KB Output is correct
5 Correct 26 ms 10604 KB Output is correct
6 Correct 30 ms 10732 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct
8 Correct 250 ms 133964 KB Output is correct
9 Correct 254 ms 131364 KB Output is correct
10 Correct 243 ms 136172 KB Output is correct
11 Correct 240 ms 130284 KB Output is correct
12 Correct 295 ms 164716 KB Output is correct
13 Correct 301 ms 167088 KB Output is correct
14 Correct 81 ms 15596 KB Output is correct
15 Correct 238 ms 106092 KB Output is correct
16 Correct 222 ms 91372 KB Output is correct
17 Correct 168 ms 86764 KB Output is correct
18 Correct 33 ms 10788 KB Output is correct
19 Correct 26 ms 10856 KB Output is correct
20 Correct 31 ms 10656 KB Output is correct
21 Correct 25 ms 10184 KB Output is correct
22 Correct 26 ms 10604 KB Output is correct
23 Correct 30 ms 10732 KB Output is correct
24 Correct 232 ms 116204 KB Output is correct
25 Correct 259 ms 118148 KB Output is correct
26 Correct 224 ms 114540 KB Output is correct
27 Correct 231 ms 114668 KB Output is correct
28 Correct 168 ms 33896 KB Output is correct
29 Correct 94 ms 16508 KB Output is correct