답안 #1007646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1007646	2024-06-25T09:43:33 Z	simona1230	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	571 ms	725396 KB

selling_rna

#include<bits/stdc++.h>
using namespace std;

struct rect
{
    int xl,xr,yl,yr;
    rect() {}
};

struct node
{
    char let;
    int l,r;
    node* c[27];
    vector<int> idx,qr;
    node()
    {
        for(int i=0; i<26; i++)
            c[i]=nullptr;
    }
};

node* pf=new node();
node* sf=new node();

int n,m;
string s[100001],pq[100001],sq[100001];
pair<int,int> p[100001];
rect q[100001];


void add(string x,int z,int t)
{
    node* curr=pf;
    for(int i=0; i<x.size(); i++)
    {
        int y=(int)(x[i]-'A');
        if(curr->c[y]==nullptr)
        {
            if(t==2)return;
            curr->c[y]=new node();
        }

        curr=curr->c[y];
        curr->let=x[i];
    }

    if(t==1)curr->idx.push_back(z);
    else curr->qr.push_back(z);

    curr=sf;
    for(int i=x.size()-1; i>=0; i--)
    {
        int y=x[i]-'A';
        if(curr->c[y]==nullptr)
            curr->c[y]=new node();

        curr=curr->c[y];
        curr->let=x[i];
    }

    curr->idx.push_back(z);
}

int num;

void dfs(node* i,int t)
{
    //cout<<i->let<<endl;
    num++;
    i->l=num;
    for(int j=0; j<i->idx.size(); j++)
    {
        if(t==1)p[i->idx[j]].first=num;
        else p[i->idx[j]].second=num;
    }
    for(int j=0; j<26; j++)
    {
        if(i->c[j]!=nullptr)
        {
            dfs(i->c[j],t);
        }
    }
    //cout<<"out"<<endl;

    i->r=num;

    for(int j=0; j<i->qr.size(); j++)
    {
        if(t==1)
        {
            q[i->qr[j]].xl=i->l;
            q[i->qr[j]].xr=i->r;
        }
        else
        {
            q[i->qr[j]].yl=i->l;
            q[i->qr[j]].yr=i->r;
        }
    }
}

void read()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>s[i];
        add(s[i],i,1);
    }

    for(int i=1; i<=m; i++)
    {
        cin>>pq[i]>>sq[i];
        node* curr=pf;
        for(int j=0; j<pq[i].size(); j++)
        {
            int y=(int)(pq[i][j]-'A');
            if(curr->c[y]==nullptr)
                break;

            curr=curr->c[y];
            if(j==pq[i].size()-1)
                curr->qr.push_back(i);
        }

        reverse(sq[i].begin(),sq[i].end());
        curr=sf;
        for(int j=0; j<sq[i].size(); j++)
        {
            int y=(int)(sq[i][j]-'A');
            if(curr->c[y]==nullptr)
                break;

            curr=curr->c[y];
            if(j==sq[i].size()-1)
                curr->qr.push_back(i);
        }

    }
}

bool cmp(pair<int,int> p1,pair<int,int> p2)
{
    return p1.second<p2.second;
}

struct line
{
    int l,r,y,i,mt;
    line(){}
    line(int _l,int _r,int _y,int _i,int _mt)
    {
        l=_l;
        r=_r;
        y=_y;
        i=_i;
        mt=_mt;
    }
};

vector<line> v;

bool cmp2(line l1,line l2)
{
    return l1.y<l2.y;
}

int t[9000001];
void update(int i,int l,int r,int idx)
{
    if(l==r)
    {
        t[i]++;
        return;
    }
    int md=(l+r)/2;
    if(idx<=md)update(i*2,l,md,idx);
    else update(i*2+1,md+1,r,idx);
    t[i]=t[i*2]+t[i*2+1];
}

int query(int i,int l,int r,int ql,int qr)
{
    //cout<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return t[i];
    int md=(l+r)/2;
    return query(i*2,l,md,ql,min(qr,md))+query(i*2+1,md+1,r,max(md+1,ql),qr);
}

int ans[100001];

void solve()
{
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(q[i].xl==0||q[i].yl==0)continue;
        v.push_back({q[i].xl,q[i].xr,q[i].yl-1,i,-1});
        v.push_back({q[i].xl,q[i].xr,q[i].yr,i,1});
    }

    sort(v.begin(),v.end(),cmp2);

    int j=1;
    for(int i=0;i<v.size();i++)
    {
        line l=v[i];
        while(j<=n&&p[j].second<=l.y)
        {
            //cout<<j<<endl;
            update(1,1,2*1e6+5,p[j].first);
            j++;
        }

        ans[l.i]+=l.mt*query(1,1,2*1e6+5,l.l,l.r);
    }

    for(int i=1;i<=m;i++)
        cout<<ans[i]<<endl;
}

int main()
{
    read();
    dfs(pf,1);
    num=0;
    dfs(sf,2);

/*
    cout<<endl;
    for(int i=1; i<=n; i++)
        cout<<p[i].first<<" "<<p[i].second<<endl;
    for(int i=1; i<=m; i++)
        cout<<q[i].xl<<" "<<q[i].xr<<" "<<q[i].yl<<" "<<q[i].yr<<endl;
    cout<<endl;
*/
    solve();

    return 0;
}

Compilation message

selling_rna.cpp: In function 'void add(std::string, int, int)':
selling_rna.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0; i<x.size(); i++)
      |                  ~^~~~~~~~~
selling_rna.cpp: In function 'void dfs(node*, int)':
selling_rna.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int j=0; j<i->idx.size(); j++)
      |                  ~^~~~~~~~~~~~~~
selling_rna.cpp:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int j=0; j<i->qr.size(); j++)
      |                  ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void read()':
selling_rna.cpp:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(int j=0; j<pq[i].size(); j++)
      |                      ~^~~~~~~~~~~~~
selling_rna.cpp:123:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             if(j==pq[i].size()-1)
      |                ~^~~~~~~~~~~~~~~~
selling_rna.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for(int j=0; j<sq[i].size(); j++)
      |                      ~^~~~~~~~~~~~~
selling_rna.cpp:136:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             if(j==sq[i].size()-1)
      |                ~^~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:207:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	13144 KB	Output is correct
2	Correct	2 ms	12892 KB	Output is correct
3	Correct	2 ms	12892 KB	Output is correct
4	Correct	3 ms	12892 KB	Output is correct
5	Correct	4 ms	9820 KB	Output is correct
6	Correct	4 ms	9820 KB	Output is correct
7	Correct	5 ms	9820 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	372 ms	574544 KB	Output is correct
2	Correct	363 ms	545932 KB	Output is correct
3	Correct	443 ms	586768 KB	Output is correct
4	Correct	395 ms	555404 KB	Output is correct
5	Correct	565 ms	714904 KB	Output is correct
6	Correct	571 ms	725396 KB	Output is correct
7	Correct	147 ms	27600 KB	Output is correct
8	Correct	407 ms	437900 KB	Output is correct
9	Correct	375 ms	368496 KB	Output is correct
10	Correct	303 ms	353464 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	22384 KB	Output is correct
2	Correct	59 ms	16352 KB	Output is correct
3	Correct	73 ms	17376 KB	Output is correct
4	Correct	62 ms	22500 KB	Output is correct
5	Correct	58 ms	24792 KB	Output is correct
6	Correct	74 ms	24804 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	13144 KB	Output is correct
2	Correct	2 ms	12892 KB	Output is correct
3	Correct	2 ms	12892 KB	Output is correct
4	Correct	3 ms	12892 KB	Output is correct
5	Correct	4 ms	9820 KB	Output is correct
6	Correct	4 ms	9820 KB	Output is correct
7	Correct	5 ms	9820 KB	Output is correct
8	Correct	372 ms	574544 KB	Output is correct
9	Correct	363 ms	545932 KB	Output is correct
10	Correct	443 ms	586768 KB	Output is correct
11	Correct	395 ms	555404 KB	Output is correct
12	Correct	565 ms	714904 KB	Output is correct
13	Correct	571 ms	725396 KB	Output is correct
14	Correct	147 ms	27600 KB	Output is correct
15	Correct	407 ms	437900 KB	Output is correct
16	Correct	375 ms	368496 KB	Output is correct
17	Correct	303 ms	353464 KB	Output is correct
18	Correct	88 ms	22384 KB	Output is correct
19	Correct	59 ms	16352 KB	Output is correct
20	Correct	73 ms	17376 KB	Output is correct
21	Correct	62 ms	22500 KB	Output is correct
22	Correct	58 ms	24792 KB	Output is correct
23	Correct	74 ms	24804 KB	Output is correct
24	Correct	360 ms	477768 KB	Output is correct
25	Correct	390 ms	479536 KB	Output is correct
26	Correct	340 ms	471444 KB	Output is correct
27	Correct	373 ms	486088 KB	Output is correct
28	Correct	326 ms	91092 KB	Output is correct
29	Correct	216 ms	28876 KB	Output is correct

답안 #1007646

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 25.0 / 25.0

Subtask #3 25.0 / 25.0

Subtask #4 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
25.0 / 25.0

Subtask #3
25.0 / 25.0

Subtask #4
40.0 / 40.0