oj.uz

Submission #239242

# Submission time Handle Problem Language Result Execution time Memory
239242 2020-06-15T00:00:04 Z m3r8 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 829 ms 30528 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7176 KB Output is correct
2 Correct 126 ms 11756 KB Output is correct
3 Correct 116 ms 11448 KB Output is correct
4 Correct 124 ms 11824 KB Output is correct
5 Correct 85 ms 8812 KB Output is correct
6 Correct 90 ms 8812 KB Output is correct
7 Correct 141 ms 11836 KB Output is correct
8 Correct 121 ms 13664 KB Output is correct
9 Correct 130 ms 13548 KB Output is correct
10 Correct 114 ms 11244 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 12324 KB Output is correct
2 Correct 132 ms 8252 KB Output is correct
3 Correct 173 ms 11056 KB Output is correct
4 Correct 137 ms 10552 KB Output is correct
5 Correct 133 ms 8512 KB Output is correct
6 Correct 177 ms 11056 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 76 ms 7176 KB Output is correct
9 Correct 126 ms 11756 KB Output is correct
10 Correct 116 ms 11448 KB Output is correct
11 Correct 124 ms 11824 KB Output is correct
12 Correct 85 ms 8812 KB Output is correct
13 Correct 90 ms 8812 KB Output is correct
14 Correct 141 ms 11836 KB Output is correct
15 Correct 121 ms 13664 KB Output is correct
16 Correct 130 ms 13548 KB Output is correct
17 Correct 114 ms 11244 KB Output is correct
18 Correct 204 ms 12324 KB Output is correct
19 Correct 132 ms 8252 KB Output is correct
20 Correct 173 ms 11056 KB Output is correct
21 Correct 137 ms 10552 KB Output is correct
22 Correct 133 ms 8512 KB Output is correct
23 Correct 177 ms 11056 KB Output is correct
24 Correct 272 ms 13580 KB Output is correct
25 Correct 493 ms 16156 KB Output is correct
26 Correct 190 ms 12840 KB Output is correct
27 Correct 273 ms 13676 KB Output is correct
28 Correct 829 ms 30528 KB Output is correct
29 Correct 507 ms 24784 KB Output is correct