Submission #1007646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007646		simona1230	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	571 ms	725396 KiB

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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40