oj.uz

Submission #204206

# Submission time Handle Problem Language Result Execution time Memory
204206 2020-02-25T08:10:22 Z amoo_safar Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 33516 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 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

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.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 22136 KB Output is correct
2 Correct 286 ms 22368 KB Output is correct
3 Correct 269 ms 22412 KB Output is correct
4 Correct 325 ms 22440 KB Output is correct
5 Correct 364 ms 17552 KB Output is correct
6 Correct 404 ms 17548 KB Output is correct
7 Correct 270 ms 24836 KB Output is correct
8 Correct 286 ms 26412 KB Output is correct
9 Correct 319 ms 26668 KB Output is correct
10 Correct 304 ms 20224 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1344 ms 15960 KB Output is correct
2 Correct 356 ms 13412 KB Output is correct
3 Correct 522 ms 15460 KB Output is correct
4 Correct 519 ms 15460 KB Output is correct
5 Correct 617 ms 13536 KB Output is correct
6 Correct 888 ms 15460 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 12 ms 9720 KB Output is correct
4 Correct 12 ms 9848 KB Output is correct
5 Correct 11 ms 9720 KB Output is correct
6 Correct 12 ms 9720 KB Output is correct
7 Correct 11 ms 9724 KB Output is correct
8 Correct 154 ms 22136 KB Output is correct
9 Correct 286 ms 22368 KB Output is correct
10 Correct 269 ms 22412 KB Output is correct
11 Correct 325 ms 22440 KB Output is correct
12 Correct 364 ms 17552 KB Output is correct
13 Correct 404 ms 17548 KB Output is correct
14 Correct 270 ms 24836 KB Output is correct
15 Correct 286 ms 26412 KB Output is correct
16 Correct 319 ms 26668 KB Output is correct
17 Correct 304 ms 20224 KB Output is correct
18 Correct 1344 ms 15960 KB Output is correct
19 Correct 356 ms 13412 KB Output is correct
20 Correct 522 ms 15460 KB Output is correct
21 Correct 519 ms 15460 KB Output is correct
22 Correct 617 ms 13536 KB Output is correct
23 Correct 888 ms 15460 KB Output is correct
24 Correct 622 ms 24112 KB Output is correct
25 Correct 1060 ms 26756 KB Output is correct
26 Correct 489 ms 23304 KB Output is correct
27 Correct 967 ms 24460 KB Output is correct
28 Execution timed out 1534 ms 33516 KB Time limit exceeded
29 Halted 0 ms 0 KB -