oj.uz

Submission #332913

# Submission time Handle Problem Language Result Execution time Memory
332913 2020-12-04T01:28:41 Z daniel920712 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 978 ms 409032 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>

using namespace std;
struct A
{
    int nxt[5];
    int con=0;
    int len;
    int l,r;
}Node[5][2000005];

struct B
{
    int l,r;
    int nxl,nxr;
    int nxt;
    int con;
}Node2[20000005];

vector < vector < int > > all[5];
vector < int > xx[5];
pair < int , int > where[100005];
char ttt[100005];
int sz[100005];
int cha[505];
int now[5]={1,1};
int tt[5]={0,0};
int now2=1,N;

int con;
void New(int x,int y,int z)
{
    Node[x][y].con=0;
    Node[x][y].nxt[0]=-1;
    Node[x][y].nxt[1]=-1;
    Node[x][y].nxt[2]=-1;
    Node[x][y].nxt[3]=-1;
    Node[x][y].len=z;
}
void build(int x,int y,int here)
{
    if(Node[x][here].len==sz[y])
    {
        Node[x][here].con++;
        return;
    }
    if(Node[x][here].nxt[all[x][y][Node[x][here].len]]==-1)
    {
        Node[x][here].nxt[all[x][y][Node[x][here].len]]=now[x]++;
        New(x,Node[x][here].nxt[all[x][y][Node[x][here].len]],Node[x][here].len+1);
    }
    build(x,y,Node[x][here].nxt[all[x][y][Node[x][here].len]]);
}
void BFS(int x,int here)
{
    int i;
    Node[x][here].l=tt[x];
    Node[x][here].r=tt[x]+Node[x][here].con-1;
    tt[x]+=Node[x][here].con;
    for(i=0;i<4;i++)
    {
        if(Node[x][here].nxt[i]!=-1)
        {
            BFS(x,Node[x][here].nxt[i]);
            Node[x][here].r=Node[x][Node[x][here].nxt[i]].r;
        }
    }
}
pair < int , int > Find(int x,int here)
{
    if(Node[x][here].len==con) return make_pair(Node[x][here].l,Node[x][here].r);
    if(Node[x][here].nxt[xx[0][Node[x][here].len]]==-1) return make_pair(-1,-1);
    return Find(x,Node[x][here].nxt[xx[0][Node[x][here].len]]);
}

void New2(int l,int r,int nxt,int here)
{
    Node2[here].l=l;
    Node2[here].r=r;
    Node2[here].nxt=nxt;
    Node2[here].nxl=-1;
    Node2[here].nxr=-1;
    Node2[here].con=0;
}
void add(int x,int y,int here)
{
    //printf("%d %d %d %d %d %d\n",x,y,here,Node2[here].l,Node2[here].r,Node2[here].nxt);
    Node2[here].con++;
    if(Node2[here].nxt==-2)
    {
        if(y==Node2[here].l&&y==Node2[here].r) return ;
        if(y<=(Node2[here].l+Node2[here].r)/2)
        {
            if(Node2[here].nxl==-1)
            {
                Node2[here].nxl=now2++;
                New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,-2,Node2[here].nxl);
            }
            add(x,y,Node2[here].nxl);
        }
        else
        {
            if(Node2[here].nxr==-1)
            {
                Node2[here].nxr=now2++;
                New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,-2,Node2[here].nxr);
            }
            add(x,y,Node2[here].nxr);
        }
    }
    else
    {
        if(Node2[here].nxt==-1)
        {
            Node2[here].nxt=now2++;
            New2(0,N,-2,Node2[here].nxt);
        }
        add(x,y,Node2[here].nxt);
        if(x==Node2[here].l&&x==Node2[here].r) return;
        if(x<=(Node2[here].l+Node2[here].r)/2)
        {
            if(Node2[here].nxl==-1)
            {
                Node2[here].nxl=now2++;
                New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,-1,Node2[here].nxl);
            }
            add(x,y,Node2[here].nxl);
        }
        else
        {
            if(Node2[here].nxr==-1)
            {
                Node2[here].nxr=now2++;
                New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,-1,Node2[here].nxr);
            }
            add(x,y,Node2[here].nxr);
        }

    }
}

int Find2(int l1,int r1,int l2,int r2,int here)
{
    if(here==-1) return 0;
    if(Node2[here].nxt==-2)
    {
        if(l2==Node2[here].l&&r2==Node2[here].r) return Node2[here].con;
        if(r2<=(Node2[here].l+Node2[here].r)/2) return Find2(l1,r1,l2,r2,Node2[here].nxl);
        else if(l2>(Node2[here].l+Node2[here].r)/2) return Find2(l1,r1,l2,r2,Node2[here].nxr);
        else return Find2(l1,r1,l2,(Node2[here].l+Node2[here].r)/2,Node2[here].nxl)+Find2(l1,r1,(Node2[here].l+Node2[here].r)/2+1,r2,Node2[here].nxr);
    }
    else
    {
        if(l1==Node2[here].l&&r1==Node2[here].r) return Find2(l1,r1,l2,r2,Node2[here].nxt);
        if(r1<=(Node2[here].l+Node2[here].r)/2) return Find2(l1,r1,l2,r2,Node2[here].nxl);
        else if(l1>(Node2[here].l+Node2[here].r)/2) return Find2(l1,r1,l2,r2,Node2[here].nxr);
        else return Find2(l1,(Node2[here].l+Node2[here].r)/2,l2,r2,Node2[here].nxl)+Find2((Node2[here].l+Node2[here].r)/2+1,r1,l2,r2,Node2[here].nxr);
    }
}

int main()
{

    pair < int , int > a,b;
    int M,K,t=0,i,j,k,t2,ans=0;
    cha['A']=0;
    cha['U']=1;
    cha['C']=2;
    cha['G']=3;
    scanf("%d %d",&N,&M);
    New2(0,N,-1,0);
    New(0,0,0);
    New(1,0,0);
    for(i=0;i<N;i++)
    {
        scanf("%s",ttt);
        sz[i]=strlen(ttt);
        xx[0].clear();
        for(j=0;j<sz[i];j++) xx[0].push_back(cha[ttt[j]]);
        xx[1].clear();
        for(j=0;j<sz[i];j++) xx[1].push_back(cha[ttt[sz[i]-j-1]]);
        all[0].push_back(xx[0]);
        all[1].push_back(xx[1]);
        build(0,i,0);
        build(1,i,0);
    }
    BFS(0,0);
    BFS(1,0);
    for(i=0;i<N;i++)
    {
        con=sz[i];
        xx[0]=all[0][i];
        where[i].first=Find(0,0).first;
        xx[0]=all[1][i];
        where[i].second=Find(1,0).first;
        add(where[i].first,where[i].second,0);
    }

    while(M--)
    {
        scanf("%s",ttt);
        xx[0].clear();
        con=strlen(ttt);
        for(j=0;j<con;j++) xx[0].push_back(cha[ttt[j]]);
        a=Find(0,0);
        scanf("%s",ttt);
        xx[0].clear();
        con=strlen(ttt);
        for(j=0;j<con;j++) xx[0].push_back(cha[ttt[con-j-1]]);
        b=Find(1,0);
        if(a.first==-1||b.first==-1) printf("0\n");
        else
        {


            printf("%d\n",Find2(a.first,a.second,b.first,b.second,0));
        }

    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:185:55: warning: array subscript has type 'char' [-Wchar-subscripts]
  185 |         for(j=0;j<sz[i];j++) xx[0].push_back(cha[ttt[j]]);
      |                                                  ~~~~~^
selling_rna.cpp:187:63: warning: array subscript has type 'char' [-Wchar-subscripts]
  187 |         for(j=0;j<sz[i];j++) xx[1].push_back(cha[ttt[sz[i]-j-1]]);
      |                                                  ~~~~~~~~~~~~~^
selling_rna.cpp:210:53: warning: array subscript has type 'char' [-Wchar-subscripts]
  210 |         for(j=0;j<con;j++) xx[0].push_back(cha[ttt[j]]);
      |                                                ~~~~~^
selling_rna.cpp:215:59: warning: array subscript has type 'char' [-Wchar-subscripts]
  215 |         for(j=0;j<con;j++) xx[0].push_back(cha[ttt[con-j-1]]);
      |                                                ~~~~~~~~~~~^
selling_rna.cpp:171:11: warning: unused variable 'K' [-Wunused-variable]
  171 |     int M,K,t=0,i,j,k,t2,ans=0;
      |           ^
selling_rna.cpp:171:13: warning: unused variable 't' [-Wunused-variable]
  171 |     int M,K,t=0,i,j,k,t2,ans=0;
      |             ^
selling_rna.cpp:171:21: warning: unused variable 'k' [-Wunused-variable]
  171 |     int M,K,t=0,i,j,k,t2,ans=0;
      |                     ^
selling_rna.cpp:171:23: warning: unused variable 't2' [-Wunused-variable]
  171 |     int M,K,t=0,i,j,k,t2,ans=0;
      |                       ^~
selling_rna.cpp:171:26: warning: unused variable 'ans' [-Wunused-variable]
  171 |     int M,K,t=0,i,j,k,t2,ans=0;
      |                          ^~~
selling_rna.cpp:176:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  176 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
selling_rna.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  182 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~
selling_rna.cpp:207:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  207 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~
selling_rna.cpp:212:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  212 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 352620 KB Output is correct
2 Correct 169 ms 352620 KB Output is correct
3 Correct 175 ms 352748 KB Output is correct
4 Correct 172 ms 352640 KB Output is correct
5 Correct 170 ms 352748 KB Output is correct
6 Correct 168 ms 352620 KB Output is correct
7 Correct 171 ms 352748 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 372448 KB Output is correct
2 Correct 409 ms 379116 KB Output is correct
3 Correct 406 ms 375148 KB Output is correct
4 Correct 409 ms 378860 KB Output is correct
5 Correct 407 ms 374764 KB Output is correct
6 Correct 398 ms 374892 KB Output is correct
7 Correct 321 ms 366700 KB Output is correct
8 Correct 428 ms 379500 KB Output is correct
9 Correct 416 ms 378348 KB Output is correct
10 Correct 366 ms 376768 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 359168 KB Output is correct
2 Correct 275 ms 360412 KB Output is correct
3 Correct 306 ms 361072 KB Output is correct
4 Correct 249 ms 357596 KB Output is correct
5 Correct 273 ms 360412 KB Output is correct
6 Correct 303 ms 361044 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 352620 KB Output is correct
2 Correct 169 ms 352620 KB Output is correct
3 Correct 175 ms 352748 KB Output is correct
4 Correct 172 ms 352640 KB Output is correct
5 Correct 170 ms 352748 KB Output is correct
6 Correct 168 ms 352620 KB Output is correct
7 Correct 171 ms 352748 KB Output is correct
8 Correct 390 ms 372448 KB Output is correct
9 Correct 409 ms 379116 KB Output is correct
10 Correct 406 ms 375148 KB Output is correct
11 Correct 409 ms 378860 KB Output is correct
12 Correct 407 ms 374764 KB Output is correct
13 Correct 398 ms 374892 KB Output is correct
14 Correct 321 ms 366700 KB Output is correct
15 Correct 428 ms 379500 KB Output is correct
16 Correct 416 ms 378348 KB Output is correct
17 Correct 366 ms 376768 KB Output is correct
18 Correct 296 ms 359168 KB Output is correct
19 Correct 275 ms 360412 KB Output is correct
20 Correct 306 ms 361072 KB Output is correct
21 Correct 249 ms 357596 KB Output is correct
22 Correct 273 ms 360412 KB Output is correct
23 Correct 303 ms 361044 KB Output is correct
24 Correct 495 ms 391780 KB Output is correct
25 Correct 576 ms 391780 KB Output is correct
26 Correct 460 ms 391396 KB Output is correct
27 Correct 496 ms 391524 KB Output is correct
28 Correct 978 ms 409032 KB Output is correct
29 Correct 525 ms 372040 KB Output is correct