제출 #26643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26643		top34051	Selling RNA Strands (JOI16_selling_rna)	C++14	60 / 100	566 ms	68104 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
struct node
{
    int x,id,type;
    node(int _x = 0,int _id = 0,int _type = 0)
    {
        x = _x; id = _id; type = _type;
    }
};
int n,m,sz;
int ans[maxn];
int pos[maxn];
int l[maxn];
int r[maxn];
int tree[maxn*4];
vector<node> p;
vector<node> q;
vector<string> s;
vector<string> t;
bool cmp1(node p1,node p2)
{
    if(s[p1.x]==s[p2.x]) return p1.type<p2.type;
    return s[p1.x]<s[p2.x];
}
bool cmp2(node p1,node p2)
{
    if(t[p1.x]==t[p2.x]) return p1.type<p2.type;
    return t[p1.x]<t[p2.x];
}
void add(int x,int val)
{
    while(x<=sz)
    {
        tree[x] += val;
        x += x&-x;
    }
}
int sum(int x)
{
    int res = 0;
    while(x>0)
    {
        res += tree[x];
        x -= x&-x;
    }
    return res;
}
main()
{
    int i,x;
    string temp,temp2;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    sz = 0;
    for(i=0;i<n;i++)
    {
        cin >> temp;
        s.push_back(temp);       p.push_back(node(sz,i,0));
        reverse(temp.begin(),temp.end());
        t.push_back(temp);       q.push_back(node(sz,i,0));
        sz += 1;
    }
    for(i=0;i<m;i++)
    {
        cin >> temp >> temp2;
        s.push_back(temp);       p.push_back(node(sz,i,-1));
        temp[temp.size()-1]++;
        s.push_back(temp);       p.push_back(node(sz+1,i,1));
        reverse(temp2.begin(),temp2.end());
        t.push_back(temp2);      q.push_back(node(sz,i,-1));
        temp2[temp2.size()-1]++;
        t.push_back(temp2);      q.push_back(node(sz+1,i,1));
        sz += 2;
    }

    sort(&p[0],&p[sz],cmp1);
    sort(&q[0],&q[sz],cmp2);

    for(i=0;i<p.size();i++)
    {
        if(p[i].type==-1) l[p[i].id] = i+1;
        if(p[i].type==0) pos[p[i].id] = i+1;
        if(p[i].type==1) r[p[i].id] = i+1;
    }

    for(i=0;i<q.size();i++)
    {
        x = q[i].id;
        if(q[i].type==-1) ans[x] -= sum(r[x])-sum(l[x]);
        if(q[i].type==0) add(pos[x],1);
        if(q[i].type==1) ans[x] += sum(r[x])-sum(l[x]);
    }

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

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp:50:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:82:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<p.size();i++)
              ^
selling_rna.cpp:89:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<q.size();i++)
              ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40