Submission #204206

#	Time	Username	Problem	Language	Result	Execution time	Memory
204206		amoo_safar	Selling RNA Strands (JOI16_selling_rna)	C++14	60 / 100	1534 ms	33516 KiB

selling_rna

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef string str;
typedef pair<str, int> T;

const int N = 1e5 + 10;

int n, m;

vector<T> V;

int fl = false;
char c = 'a'; //'#'
bool CMP(T A, T B){
	if(fl) c = '#';
	else c = 'a';
	int ln = min(A.F.size(), B.F.size());
	if(A.S < 0) A.F += c;
	else A.F += 'A';
	if(B.S < 0) B.F += c;
	else B.F += 'A';
	return A < B;
	/*
	for(int i = 0; i < ln; i++){
		if(A.F[i] != B.F[i]) return A.F[i] < B.F[i];
	}
	if(A.S < 0 && B.S < 0) return A.F.size() < B.F.size();
	if(A.S > 0 && B.S > 0) return A.F.size() < B.F.size();
	//if(fl) return A.S < 0;

	//if(A.S < 0 && B.S > 0 && A.F.size() > B.F.size()) return false;
	//if(A.S > 0 && B.S < 0 && A.F.size() < B.F.size()) return true;
	if(fl) return A.S < B.S;
	return A.S > B.S;
	*/
}

str R[N], P[N], Q[N];
int st[N], SQ[N], FQ[N], SQ2[N], FQ2[N];
vector<int> ord;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> R[i];
	for(int j = 1; j <= m; j++) cin >> P[j] >> Q[j];

	for(int i = 1; i <= n; i++) V.pb({R[i], i});
	for(int i = 1; i <= m; i++) V.pb({P[i], -i});
	sort(all(V), CMP);
	int la = 1;
	for(auto &x : V){
		if(x.S < 0) FQ[-x.S] = la;
		else st[x.S] = la ++;
	}
	//cerr << '\n';
	//for(auto x : V) cerr << x.F << " " << x.S << '\n';
	fl = true;
	sort(all(V), CMP);
	la = 1;
	for(auto &x : V){
		if(x.S < 0) SQ[-x.S] = la;
		else la ++;
	}
	//cerr << '\n';
	//for(auto x : V) cerr << x.F << " " << x.S << '\n';
	//cerr << '\n';
	/*
	for(int i = 1; i <= n; i++) cerr << st[i] << ' ';
	cerr << '\n';
	for(int i = 1; i <= m; i++) cerr << "[" << SQ[i] << ", " << FQ[i] << ")\n";
	cerr << '\n';
	for(auto x : V) cerr << x.F << " " << x.S << '\n';
	*/
	V.clear();
	for(int i = 1; i <= n; i++){
		reverse(all(R[i]));
		V.pb({R[i], st[i]});
	}
	for(int i = 1; i <= m; i++){
		reverse(all(Q[i]));
		V.pb({Q[i], -i});
	}
	sort(all(V), CMP);
	for(auto &x : V){
		if(0 < x.S) ord.pb(x.S);
		else SQ2[-x.S] = ord.size();
	}
	fl = false;
	sort(all(V), CMP);
	ord.clear();
	for(auto &x : V){
		if(0 < x.S) ord.pb(x.S);
		else FQ2[-x.S] = ord.size();
	}
	

	//for(auto x : ord) cerr << x << ' ';
	//cerr << '\n';
	//for(int i = 1; i <= m; i++) cerr << "[" << SQ[i] << ", " << FQ[i] << ") [" << SQ2[i] << ", " << FQ2[i] << ")\n";
	//cerr << '\n';
	for(int i = 1; i <= m; i++){
		int res = 0;
		for(int j = SQ2[i]; j < FQ2[i]; j++) res += (SQ[i] <= ord[j] && ord[j] < FQ[i]);
		cout << res << '\n';
	}
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'bool CMP(T, T)':
selling_rna.cpp:25:6: warning: unused variable 'ln' [-Wunused-variable]
  int ln = min(A.F.size(), B.F.size());
      ^~

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