oj.uz

Submission #383312

# Submission time Handle Problem Language Result Execution time Memory
383312 2021-03-29T14:54:09 Z MODDI Mountains (NOI20_mountains) C++14
24 / 100
 905 ms 109780 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n;
vl arr;
vector<ll> tree[12 * 100000];
void build(int node, int l, int r){
	if(l == r)
		tree[node].pb(arr[l]);
	else{
		int mid = (l + r) / 2;
		build(node * 2, l, mid);
		build(node * 2 + 1, mid + 1, r);
		merge(tree[node * 2].begin(), tree[node * 2].end(), tree[node * 2 + 1].begin(), tree[node * 2 + 1].end(), back_inserter(tree[node]));
	}
}
int query(int node, int l, int r, int L, int R, int k){
	if(r < L || l > R)	return 0;
	if(L <= l && r <= R){
		return lower_bound(tree[node].begin(), tree[node].end(), k) -tree[node].begin();
	}
	int mid = (l + r) / 2;
	int left = query(node  * 2, l, mid, L, R, k), right = query(node * 2 + 1, mid + 1, r, L, R, k);
	return left + right;
}
int main(){
	cin>>n;
	for(int i = 0; i < n; i++){
		ll a;
		cin>>a;
		arr.pb(a);
	}
	build(1, 0, n - 1);
	ll rez = 0;
	for(int i =1; i < n - 1; i++){
		ll left = query(1, 0, n - 1, 0, i, arr[i]);
		ll right = query(1, 0, n - 1, i, n - 1, arr[i]);
		if(left > 0 && right > 0)
			rez += (left * right);
	}
	cout<<rez<<endl;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28524 KB Output is correct
2 Correct 621 ms 107788 KB Output is correct
3 Correct 639 ms 107856 KB Output is correct
4 Correct 627 ms 107732 KB Output is correct
5 Correct 614 ms 107748 KB Output is correct
6 Correct 620 ms 107860 KB Output is correct
7 Correct 618 ms 107768 KB Output is correct
8 Correct 613 ms 107860 KB Output is correct
9 Correct 662 ms 107860 KB Output is correct
10 Correct 617 ms 107732 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 107732 KB Output is correct
2 Correct 478 ms 108372 KB Output is correct
3 Correct 473 ms 108372 KB Output is correct
4 Correct 498 ms 108372 KB Output is correct
5 Correct 487 ms 108504 KB Output is correct
6 Correct 474 ms 108372 KB Output is correct
7 Correct 473 ms 108372 KB Output is correct
8 Correct 460 ms 108372 KB Output is correct
9 Correct 461 ms 108284 KB Output is correct
10 Correct 19 ms 28524 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 107732 KB Output is correct
2 Correct 478 ms 108372 KB Output is correct
3 Correct 473 ms 108372 KB Output is correct
4 Correct 498 ms 108372 KB Output is correct
5 Correct 487 ms 108504 KB Output is correct
6 Correct 474 ms 108372 KB Output is correct
7 Correct 473 ms 108372 KB Output is correct
8 Correct 460 ms 108372 KB Output is correct
9 Correct 461 ms 108284 KB Output is correct
10 Correct 19 ms 28524 KB Output is correct
11 Correct 751 ms 108756 KB Output is correct
12 Correct 742 ms 108628 KB Output is correct
13 Correct 748 ms 108728 KB Output is correct
14 Correct 751 ms 108756 KB Output is correct
15 Correct 748 ms 108712 KB Output is correct
16 Correct 775 ms 108664 KB Output is correct
17 Correct 773 ms 108600 KB Output is correct
18 Correct 457 ms 108756 KB Output is correct
19 Correct 453 ms 108680 KB Output is correct
20 Correct 19 ms 28524 KB Output is correct

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 28524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 28524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 107732 KB Output is correct
2 Correct 478 ms 108372 KB Output is correct
3 Correct 473 ms 108372 KB Output is correct
4 Correct 498 ms 108372 KB Output is correct
5 Correct 487 ms 108504 KB Output is correct
6 Correct 474 ms 108372 KB Output is correct
7 Correct 473 ms 108372 KB Output is correct
8 Correct 460 ms 108372 KB Output is correct
9 Correct 461 ms 108284 KB Output is correct
10 Correct 19 ms 28524 KB Output is correct
11 Correct 751 ms 108756 KB Output is correct
12 Correct 742 ms 108628 KB Output is correct
13 Correct 748 ms 108728 KB Output is correct
14 Correct 751 ms 108756 KB Output is correct
15 Correct 748 ms 108712 KB Output is correct
16 Correct 775 ms 108664 KB Output is correct
17 Correct 773 ms 108600 KB Output is correct
18 Correct 457 ms 108756 KB Output is correct
19 Correct 453 ms 108680 KB Output is correct
20 Correct 19 ms 28524 KB Output is correct
21 Correct 872 ms 109652 KB Output is correct
22 Correct 905 ms 109652 KB Output is correct
23 Correct 864 ms 109652 KB Output is correct
24 Correct 863 ms 109652 KB Output is correct
25 Correct 873 ms 109780 KB Output is correct
26 Correct 870 ms 109780 KB Output is correct
27 Correct 866 ms 109524 KB Output is correct
28 Correct 485 ms 109524 KB Output is correct
29 Correct 481 ms 109524 KB Output is correct
30 Correct 20 ms 28524 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28524 KB Output is correct
2 Correct 621 ms 107788 KB Output is correct
3 Correct 639 ms 107856 KB Output is correct
4 Correct 627 ms 107732 KB Output is correct
5 Correct 614 ms 107748 KB Output is correct
6 Correct 620 ms 107860 KB Output is correct
7 Correct 618 ms 107768 KB Output is correct
8 Correct 613 ms 107860 KB Output is correct
9 Correct 662 ms 107860 KB Output is correct
10 Correct 617 ms 107732 KB Output is correct
11 Correct 471 ms 107732 KB Output is correct
12 Correct 478 ms 108372 KB Output is correct
13 Correct 473 ms 108372 KB Output is correct
14 Correct 498 ms 108372 KB Output is correct
15 Correct 487 ms 108504 KB Output is correct
16 Correct 474 ms 108372 KB Output is correct
17 Correct 473 ms 108372 KB Output is correct
18 Correct 460 ms 108372 KB Output is correct
19 Correct 461 ms 108284 KB Output is correct
20 Correct 19 ms 28524 KB Output is correct
21 Correct 751 ms 108756 KB Output is correct
22 Correct 742 ms 108628 KB Output is correct
23 Correct 748 ms 108728 KB Output is correct
24 Correct 751 ms 108756 KB Output is correct
25 Correct 748 ms 108712 KB Output is correct
26 Correct 775 ms 108664 KB Output is correct
27 Correct 773 ms 108600 KB Output is correct
28 Correct 457 ms 108756 KB Output is correct
29 Correct 453 ms 108680 KB Output is correct
30 Correct 19 ms 28524 KB Output is correct
31 Incorrect 19 ms 28524 KB Output isn't correct
32 Halted 0 ms 0 KB -