Submission #95920

#	Time	Username	Problem	Language	Result	Execution time	Memory
95920		Retro3014	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	675 ms	72908 KiB

selling_rna

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;
typedef long long ll;
#define MAX_M 100000

int N, M;
vector<string> S, P, Q;
string str;
struct ST{
	ST (string s, int idx, bool b1, bool b2) : s(s), idx(idx), b1(b1), b2(b2) {}
	string s;
	int idx;
	bool b1, b2;
	bool operator <(const ST &a)const{
		return s<a.s;
	}
};
vector<ST> v1, v2;
struct PT{
	PT (int x, int y) : x(x), y(y) {}
	int x, y;
};
vector<PT> vS, vP[2];

struct SEG{
	SEG (int sum, int l, int r) : sum(sum), l(l), r(r) {}
	int sum;
	int l, r;
};
vector<SEG> seg;

void update(int idx, int s, int e, int k){
	seg[idx].sum++;
	if(s==e)	return;
	if(k<=(s+e)/2){
		if(seg[idx].l==-1){
			seg[idx].l = seg.size();
			seg.push_back({0, -1, -1});
		}
		update(seg[idx].l, s, (s+e)/2, k);
	}else{
		if(seg[idx].r==-1){
			seg[idx].r = seg.size();
			seg.push_back({0, -1, -1});
		}
		update(seg[idx].r, (s+e)/2+1, e, k);
	}
}

int sum(int idx, int s, int e, int x, int y){
	if(idx==-1)	return 0;
	if(x<=s && e<=y)	return seg[idx].sum;
	if(x>e || y<s)	return 0;
	return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
}

struct S2{
	S2 (int idx, int type, int x1, int x2, int y) : idx(idx), type(type), x1(x1), x2(x2), y(y) {}
	int idx, type;
	int x1, x2, y;
	bool operator <(const S2 &a)const{
		if(y==a.y){
			return type<a.type;
		}
		return y<a.y;
	}
};

vector<S2> query;
int ans[MAX_M+1];

int main(){
	seg.push_back({0, -1, -1});
	scanf("%d%d", &N, &M);
	for(int i=0; i<N; i++){
		vS.push_back({0, 0});
		cin>>str;	S.push_back(str);
		//cout<<str<<endl;
		v1.push_back({S[i], i, 1, 0});
		for(int j=0; j<S[i].size(); j++){
			str[j] = S[i][S[i].size()-j-1];
		}
		//cout<<str<<endl;
		v2.push_back({str, i, 1, 0});
	}
	for(int i=0; i<M; i++){
		vP[0].push_back({0, 0});
		vP[1].push_back({0, 0});
		cin>>str; P.push_back(str);
		//cout<<str<<endl;
		v1.push_back({P[i], i, 0, 0});
		str[str.size()-1]++;
		//cout<<str<<endl;
		v1.push_back({str, i, 0, 1});
		cin>>str;
		Q.push_back(str);
		for(int j=0; j<Q[i].size(); j++){
			str[j] = Q[i][Q[i].size()-1-j];
		}
		Q[i] = str;
		//cout<<str<<endl;
		v2.push_back({Q[i], i, 0, 0});
		str[str.size()-1]++;
		//cout<<str<<endl;
		v2.push_back({str, i, 0, 1});
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	int index = 0;
	for(int i=0; i<v1.size(); i++){
		//cout<<v1[i].s<<' '<<v1[i].idx<<endl;
		if(i!=0 && v1[i].s!=v1[i-1].s)	index++;
		if(v1[i].b1){
			vS[v1[i].idx].x = index;
		}else{
			if(v1[i].b2){
				vP[1][v1[i].idx].x = index;
			}else{
				vP[0][v1[i].idx].x = index;
			}
		}
	}//cout<<endl;
	index = 0;
	for(int i=0; i<v2.size(); i++){
		//cout<<v2[i].s<<' '<<v2[i].idx<<' '<<endl;
		if(i!=0 && v2[i].s!=v2[i-1].s)	index++;
		if(v2[i].b1){
			vS[v2[i].idx].y = index;
		}else{
			if(v2[i].b2){
				vP[1][v2[i].idx].y = index;
			}else{
				vP[0][v2[i].idx].y = index-1;
			}
		}
	}
	for(int i=0; i<vS.size(); i++){
		query.push_back({i, 0, vS[i].x, 0, vS[i].y});
	}
	for(int i=0; i<vP[0].size(); i++){
		query.push_back({i, 1, vP[0][i].x, vP[1][i].x, vP[0][i].y});
		query.push_back({i, 2, vP[0][i].x, vP[1][i].x, vP[1][i].y});
	}
	sort(query.begin(), query.end());
	for(int i=0; i<query.size(); i++){
		S2 now = query[i];
		if(now.type==0){
			//cout<<now.idx<<endl;
			update(0, 0, v1.size(), now.x1);
		}else if(now.type==1){
			//cout<<now.idx<<' '<<-1<<endl;
			ans[now.idx]-=sum(0, 0, v1.size(), now.x1, now.x2);
		}else{
			//cout<<now.idx<<' '<<1<<endl;
			ans[now.idx]+=sum(0, 0, v1.size(), now.x1, now.x2);
		}
	}
	for(int i=0; i<M; i++){
		printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<S[i].size(); j++){
                ~^~~~~~~~~~~~
selling_rna.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<Q[i].size(); j++){
                ~^~~~~~~~~~~~
selling_rna.cpp:115:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v1.size(); i++){
               ~^~~~~~~~~~
selling_rna.cpp:129:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v2.size(); i++){
               ~^~~~~~~~~~
selling_rna.cpp:142:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vS.size(); i++){
               ~^~~~~~~~~~
selling_rna.cpp:145:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vP[0].size(); i++){
               ~^~~~~~~~~~~~~
selling_rna.cpp:150:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<query.size(); i++){
               ~^~~~~~~~~~~~~
selling_rna.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~

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