oj.uz

Submission #204210

# Submission time Handle Problem Language Result Execution time Memory
204210 2020-02-25T08:15:43 Z amoo_safar Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 30060 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 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 'bool CMP(T, T)':
selling_rna.cpp:25:6: warning: unused variable 'ln' [-Wunused-variable]
  int ln = min(A.F.size(), B.F.size());
      ^~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:140: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 19 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 9848 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 19064 KB Output is correct
2 Correct 289 ms 19428 KB Output is correct
3 Correct 243 ms 19600 KB Output is correct
4 Correct 325 ms 19752 KB Output is correct
5 Correct 363 ms 16272 KB Output is correct
6 Correct 401 ms 16272 KB Output is correct
7 Correct 261 ms 20356 KB Output is correct
8 Correct 291 ms 21804 KB Output is correct
9 Correct 320 ms 21804 KB Output is correct
10 Correct 272 ms 18176 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 19292 KB Output is correct
2 Correct 290 ms 15424 KB Output is correct
3 Correct 399 ms 17372 KB Output is correct
4 Correct 348 ms 16476 KB Output is correct
5 Correct 301 ms 15328 KB Output is correct
6 Correct 420 ms 17500 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct
2 Correct 19 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 9848 KB Output is correct
8 Correct 147 ms 19064 KB Output is correct
9 Correct 289 ms 19428 KB Output is correct
10 Correct 243 ms 19600 KB Output is correct
11 Correct 325 ms 19752 KB Output is correct
12 Correct 363 ms 16272 KB Output is correct
13 Correct 401 ms 16272 KB Output is correct
14 Correct 261 ms 20356 KB Output is correct
15 Correct 291 ms 21804 KB Output is correct
16 Correct 320 ms 21804 KB Output is correct
17 Correct 272 ms 18176 KB Output is correct
18 Correct 483 ms 19292 KB Output is correct
19 Correct 290 ms 15424 KB Output is correct
20 Correct 399 ms 17372 KB Output is correct
21 Correct 348 ms 16476 KB Output is correct
22 Correct 301 ms 15328 KB Output is correct
23 Correct 420 ms 17500 KB Output is correct
24 Correct 597 ms 21724 KB Output is correct
25 Correct 993 ms 23940 KB Output is correct
26 Correct 449 ms 20872 KB Output is correct
27 Correct 645 ms 21668 KB Output is correct
28 Execution timed out 1564 ms 30060 KB Time limit exceeded
29 Halted 0 ms 0 KB -