oj.uz

Submission #540979

# Submission time Handle Problem Language Result Execution time Memory
540979 2022-03-22T05:41:03 Z l3nl3 Mountains (NOI20_mountains) C++14
0 / 100
 165 ms 41772 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 = 1e6;

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 = 100;
	a[0].first = -100;
	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 Incorrect 12 ms 31572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 41036 KB Output is correct
2 Correct 157 ms 41560 KB Output is correct
3 Correct 161 ms 41576 KB Output is correct
4 Correct 151 ms 41520 KB Output is correct
5 Correct 165 ms 41696 KB Output is correct
6 Correct 153 ms 41580 KB Output is correct
7 Correct 154 ms 41624 KB Output is correct
8 Correct 130 ms 41544 KB Output is correct
9 Correct 140 ms 41772 KB Output is correct
10 Incorrect 13 ms 31572 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 41036 KB Output is correct
2 Correct 157 ms 41560 KB Output is correct
3 Correct 161 ms 41576 KB Output is correct
4 Correct 151 ms 41520 KB Output is correct
5 Correct 165 ms 41696 KB Output is correct
6 Correct 153 ms 41580 KB Output is correct
7 Correct 154 ms 41624 KB Output is correct
8 Correct 130 ms 41544 KB Output is correct
9 Correct 140 ms 41772 KB Output is correct
10 Incorrect 13 ms 31572 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

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

Subtask #5
0 / 28.0

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

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 41036 KB Output is correct
2 Correct 157 ms 41560 KB Output is correct
3 Correct 161 ms 41576 KB Output is correct
4 Correct 151 ms 41520 KB Output is correct
5 Correct 165 ms 41696 KB Output is correct
6 Correct 153 ms 41580 KB Output is correct
7 Correct 154 ms 41624 KB Output is correct
8 Correct 130 ms 41544 KB Output is correct
9 Correct 140 ms 41772 KB Output is correct
10 Incorrect 13 ms 31572 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

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