oj.uz

답안 #365415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
365415 2021-02-11T15:46:52 Z BartolM Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 243 ms 137964 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);
        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:124:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |         scanf("%s", inp);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 8172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 243 ms 137964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 10916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 8172 KB Output isn't correct
2 Halted 0 ms 0 KB -