#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 = std::min(a.first.size(),b.first.size());
for(int i = 0;i<ln;i++){
if(a.first[i] != b.first[i])return a.first[i] < b.first[i];
};
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:105:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<inpp.size();i++){
~^~~~~~~~~~~~
selling_rna.cpp:114:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<inps.size();i++){
~^~~~~~~~~~~~
selling_rna.cpp:169:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(idx < et.size() && et[idx].first == i){
~~~~^~~~~~~~~~~
selling_rna.cpp:184:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 1;j<sol[i].size()-1;j++){
~^~~~~~~~~~~~~~~~
selling_rna.cpp:89: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:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",str);
~~~~~^~~~~~~~~~
selling_rna.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",str);
~~~~~^~~~~~~~~~
selling_rna.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",strr);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
11000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
195 ms |
12452 KB |
Output is correct |
| 2 |
Incorrect |
121 ms |
8508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
