oj.uz

Submission #540976

# Submission time Handle Problem Language Result Execution time Memory
540976 2022-03-22T05:39:13 Z l3nl3 Mountains (NOI20_mountains) C++17
64 / 100
 66 ms 17044 KB 
/*#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 7;

int n, b[N], p[N], t[N*4], ans;
pair<int, int> a[N];

void clr() {
	for (int i = 1; i < N*4; i++) {
		t[i] = 0;
	}
	return;
}

void build (int v, int tl, int tr) {
	if (tl == tr) {
		t[v] = 0;
		return;
	}
	int tm = (tl+tr) / 2;
	build(v+v, tl, tm);
	build(v+v+1, tm+1, tr);
	t[v] = t[v+v] + t[v+v+1];
}

void upd (int v, int tl, int tr, int p) {
	if (tl == tr) {
		t[v]++;
		return;
	}
	int tm = (tl+tr) / 2;
	if (p <= tm) upd(v+v, tl, tm, p);
	else upd(v+v+1, tm+1, tr, p);
	t[v] = t[v+v] + t[v+v+1];
}

int get (int v, int tl, int tr, int l, int r) {
	if (l <= tl && tr <= r) return t[v];
	if (tr < l || r < tl) return 0;
	int tm = (tl+tr) / 2;
	return get(v+v, tl, tm, l, r) + get(v+v+1, tm+1, tr, l, r);
}

signed main () {
 	//freopen("", "r", stdin);
 	//freopen("", "w", stdout);
 	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a+1, a+n+1);
	int num = 0;
	a[0].first = -1;
	for (int i = 1; i <= n; i++) {
		if (a[i].first > a[i-1].first) num++;
		b[a[i].second] = num;
	}
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		p[i] = get(1, 1, n, 1, b[i] - 1);
		upd(1, 1, n, b[i]);
	}     
	clr();
	reverse(b+1, b+n+1);
	build(1, 1,n);
	for (int i = 1; i <= n; i++) {
		int j = n-i+1;
		ans += p[j] * get(1, 1, n, 1, b[i]-1);
		upd(1, 1, n, b[i]);
	}	
	cout << ans;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Runtime error 66 ms 17044 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 12136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 12136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 9 ms 3924 KB Output is correct
12 Correct 9 ms 3924 KB Output is correct
13 Correct 10 ms 3932 KB Output is correct
14 Correct 9 ms 3924 KB Output is correct
15 Correct 9 ms 3924 KB Output is correct
16 Correct 9 ms 3932 KB Output is correct
17 Correct 9 ms 3932 KB Output is correct
18 Correct 9 ms 3924 KB Output is correct
19 Correct 7 ms 3796 KB Output is correct
20 Correct 2 ms 3408 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 12136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Runtime error 66 ms 17044 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -