oj.uz

Submission #204215

# Submission time Handle Problem Language Result Execution time Memory
204215 2020-02-25T08:18:13 Z amoo_safar Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1087 ms 42604 KB 
#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;
}
/*

*/

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 22520 KB Output is correct
2 Correct 83 ms 22928 KB Output is correct
3 Correct 77 ms 23112 KB Output is correct
4 Correct 93 ms 23360 KB Output is correct
5 Correct 79 ms 17844 KB Output is correct
6 Correct 83 ms 17904 KB Output is correct
7 Correct 80 ms 23420 KB Output is correct
8 Correct 90 ms 25484 KB Output is correct
9 Correct 94 ms 25356 KB Output is correct
10 Correct 74 ms 20508 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 18908 KB Output is correct
2 Correct 245 ms 15076 KB Output is correct
3 Correct 328 ms 17116 KB Output is correct
4 Correct 283 ms 15832 KB Output is correct
5 Correct 255 ms 15060 KB Output is correct
6 Correct 341 ms 16984 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct
2 Correct 11 ms 9848 KB Output is correct
3 Correct 11 ms 9848 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 11 ms 9848 KB Output is correct
6 Correct 11 ms 9848 KB Output is correct
7 Correct 11 ms 9764 KB Output is correct
8 Correct 50 ms 22520 KB Output is correct
9 Correct 83 ms 22928 KB Output is correct
10 Correct 77 ms 23112 KB Output is correct
11 Correct 93 ms 23360 KB Output is correct
12 Correct 79 ms 17844 KB Output is correct
13 Correct 83 ms 17904 KB Output is correct
14 Correct 80 ms 23420 KB Output is correct
15 Correct 90 ms 25484 KB Output is correct
16 Correct 94 ms 25356 KB Output is correct
17 Correct 74 ms 20508 KB Output is correct
18 Correct 407 ms 18908 KB Output is correct
19 Correct 245 ms 15076 KB Output is correct
20 Correct 328 ms 17116 KB Output is correct
21 Correct 283 ms 15832 KB Output is correct
22 Correct 255 ms 15060 KB Output is correct
23 Correct 341 ms 16984 KB Output is correct
24 Correct 192 ms 24456 KB Output is correct
25 Correct 352 ms 27780 KB Output is correct
26 Correct 150 ms 23560 KB Output is correct
27 Correct 207 ms 25640 KB Output is correct
28 Correct 1087 ms 42604 KB Output is correct
29 Correct 963 ms 31308 KB Output is correct