Submission #239242

#	Time	Username	Problem	Language	Result	Execution time	Memory
239242		m3r8	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	829 ms	30528 KiB

selling_rna

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <set>

#define N 100100
#define frm std::pair<std::string,int>
#define qry std::pair<int,std::pair<std::string,std::string>>
#define evt std::pair<int,std::pair<int,int>>
#define left(i) (i<<1)
#define right(i) ((i<<1)+1)


char str[N];
char strr[N];

std::vector<frm> inpp;
std::vector<frm> inps;

std::vector<qry> mp;
std::vector<evt> et;
std::vector<int> sol[N];

std::set<int> stt;

int pidx[N];
int n,m;

typedef struct trr{
  int val;  
  int lz;
}trr;

trr seg[N*4];

void prop(int idx, int l, int r){
  if(seg[idx].lz){
    if(l != r-1){
      seg[left(idx)].lz += seg[idx].lz;
      seg[right(idx)].lz += seg[idx].lz;
    };
    seg[idx].val += seg[idx].lz;
    seg[idx].lz = 0;
  };  
};


void update(int idx, int l, int r, int a, int b){
  if(l >= r)return;  
  if(l >= b || a >= r)return;
  if(a <= l && r <= b){
    //printf("upd: %d %d %d\n",l,r,idx);
    seg[idx].lz += 1;  
  }else{
    int m = (l + r)>>1;
    update(left(idx),l,m,a,b);
    update(right(idx),m,r,a,b);
  };
};


int qurry(int idx, int l, int r, int x){
  prop(idx,l,r);
  if(l == r-1){
    //printf("qu: %d %d %d %d\n",l,r,seg[idx].lz,idx);
    return seg[idx].val;  
  }else{
    int m = (l + r)>>1;  
    if(m > x){
      return qurry(left(idx),l,m,x);  
    }else{
      return qurry(right(idx),m,r,x);  
    };
  };
};

int cmp(frm a, frm b){
  int ln;
  int s11 = a.first.size();
  int s12 = b.first.size();
  ln = std::min(s11,s12);
  for(int i = 0;i<ln;i++){
    if(a.first[i] != b.first[i])return a.first[i] < b.first[i];  
  };
  if(s12 > s11 && b.second == -1)return 1;
  return 0;
};

int main(void){
  scanf("%d %d",&n,&m);

  std::string ss1;
  std::string ss2;

  for(int i = 0;i<n;i++){
    scanf("%s",str);  
    ss1 = std::string(str);
    inpp.push_back({ss1,i});
    ss2 = std::string(ss1);
    std::reverse(ss2.begin(),ss2.end());
    inps.push_back({ss2,i});
  };

  std::sort(inpp.begin(),inpp.end(),std::less<frm>());

  for(int i = 0;i<inpp.size();i++){
    inps[inpp[i].second].second = i;
    inpp[i].second = i;  
  };

  std::sort(inps.begin(),inps.end(),std::less<frm>());

  //printf("%d\n",inps.size());

  for(int i = 0;i<inps.size();i++){
    //printf("%d %s\n",inpp[i].second,inpp[i].first.c_str());
    //printf("%d %s\n",inps[i].second,inps[i].first.c_str());
    frm akt = inps[i];   
    pidx[akt.second] = i;
  };

  for(int i = 0;i<m;i++){
    scanf("%s",str);  
    scanf("%s",strr);
    ss1 = std::string(str);
    ss2 = std::string(strr);
    std::reverse(ss2.begin(),ss2.end());

    auto pp = std::equal_range(inpp.begin(),inpp.end(),frm(ss1,-1),cmp);
    auto ss = std::equal_range(inps.begin(),inps.end(),frm(ss2,-1),cmp);

    int p1 = pp.first - inpp.begin();
    int p2 = pp.second - inpp.begin();
    int s1 = ss.first - inps.begin();
    int s2 = ss.second - inps.begin();

    //printf("%d %d %d %d\n",p1,p2,s1,s2);
    et.push_back({p1,{s1,i}});
    et.push_back({p1,{s2,i}});
    et.push_back({p2,{s1,i}});
    et.push_back({p2,{s2,i}});

  };


  std::sort(et.begin(),et.end(),std::less<evt>());

  int idx = 0;
  /*
  puts("");
  for(auto j: et){
    printf("%d %d %d\n",j.first,j.second.first,j.second.second);  
  };

  */
  /*
  for(int i = 0;i<n;i++){
    printf("pidx: %d\n",pidx[i]);  
  };

  puts("");
  */
  
  while(et[idx].first == 0){
    sol[et[idx].second.second].push_back(0);
    idx++;  
  };
  for(int i = 1;i<=n;i++){
    update(1,0,n,pidx[i-1],n);
    while(idx < et.size() && et[idx].first == i){
      //printf("%d %d %d %d\n",et[idx].first,et[idx].second.first,et[idx].second.second,idx);
      int tmp = 0;
      if(et[idx].second.first > 0){
        tmp = qurry(1,0,n,et[idx].second.first-1);
        //printf("tmp: %d\n",tmp);
      };
      sol[et[idx].second.second].push_back(tmp);
      idx++;
    };
  };

  for(int i = 0;i<m;i++){
    int erg = 0;
    if(sol[i].size()){
      for(int j = 1;j<sol[i].size()-1;j++){
        erg -= sol[i][j];  
      };
      erg += sol[i][sol[i].size()-1] + sol[i][0];
    };
    printf("%d\n",erg);
  };
  return 0;
};

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:109:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<inpp.size();i++){
                 ~^~~~~~~~~~~~
selling_rna.cpp:118:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<inps.size();i++){
                 ~^~~~~~~~~~~~
selling_rna.cpp:173:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(idx < et.size() && et[idx].first == i){
           ~~~~^~~~~~~~~~~
selling_rna.cpp:188:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 1;j<sol[i].size()-1;j++){
                     ~^~~~~~~~~~~~~~~~
selling_rna.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&m);
   ~~~~~^~~~~~~~~~~~~~~
selling_rna.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",str);  
     ~~~~~^~~~~~~~~~
selling_rna.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",str);  
     ~~~~~^~~~~~~~~~
selling_rna.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",strr);
     ~~~~~^~~~~~~~~~~

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