제출 #204215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204215		amoo_safar	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	1087 ms	42604 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 Rs;
bool CMP(T &A, T &B){
	if(fl) c = '#';
	else c = 'a';
	if(A.S < 0) A.F += c;
	else A.F += 'A';
	if(B.S < 0) B.F += c;
	else B.F += 'A';
	Rs = (A < B);
	A.F.pop_back();
	B.F.pop_back();
	return Rs;
	/*
	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 seg[20][N];
int LG(int id, int x, int L, int R, int d){
	int idx = lower_bound(seg[d] + L, seg[d] + R, x) - seg[d];
	return idx - L;	
}

void Build(int id, int L, int R, int d = 0){
	if(L + 1 == R){
		seg[d][L] = ord[L];
		return ;
	}
	int mid = (L + R) >> 1;
	Build(id << 1, L, mid, d + 1);
	Build(id << 1 | 1, mid, R, d + 1);
	merge(seg[d + 1] + L, seg[d + 1] + mid, seg[d + 1] + mid, seg[d + 1] + R, seg[d] + L);
	return ;
}
int Query(int id, int l, int r, int x, int L, int R, int d = 0){
	if(r <= L || R <= l) return 0;
	if(l <= L && R <= r) return LG(id, x, L, R, d); //{Less(id, x), Great(id, x)};
	int mid = (L + R) >> 1;
	int A = Query(id << 1, l, r, x, L, mid, d + 1);
	int B = Query(id << 1 | 1, l, r, x, mid, R, d + 1);
	return A + B;
}


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';
	Build(1, 0, 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 << Query(1, SQ2[i], FQ2[i], FQ[i], 0, n) - Query(1, SQ2[i], FQ2[i], SQ[i], 0, n) << '\n';
	}
	return 0;
}
/*

*/

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:143:7: warning: unused variable 'res' [-Wunused-variable]
   int res = 0;
       ^~~

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