oj.uz

Submission #632479

# Submission time Handle Problem Language Result Execution time Memory
632479 2022-08-20T07:23:17 Z shmad Mountains (NOI20_mountains) C++17
24 / 100
 437 ms 98228 KB 
#pragma GCC optimize("O3", "unroll-loops") // "Ofast" 	
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

//#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvt = vt< vt<int> >;

const int N = 1e6 + 5, mod = 1e9 + 7, B = 500;
const ll inf = 1e18 + 7, LIM = (1ll << 60);
const double eps = 1e-6;

int n;;
map<ll, int> m;
set<ll> st;
ll h[N], t[4 * N];

void upd (int pos, int v = 1, int tl = 1, int tr = N) {
	if (tl == tr) {
		t[v]++;
		return;
	}
	int tm = tl + tr >> 1;
	if (pos <= tm) upd(pos, v << 1, tl, tm);
	else upd(pos, v << 1 | 1, tm + 1, tr);
	t[v] = t[v << 1] + t[v << 1 | 1];
}

ll get (int l, int r, int v = 1, int tl = 1, int tr = N) {
	if (tl > r || tr < l) return 0ll;
	if (tl >= l && tr <= r) return t[v];
	int tm = tl + tr >> 1;
	ll a = get(l, r, v << 1, tl, tm);
	ll b = get(l, r, v << 1 | 1, tm + 1, tr);
	return (a + b);
}

ll l[N], r[N];

void solve () {
	cin >> n;
	vt<int> p(n + 1, 0), s(n + 2, 0);
	for (int i = 1; i <= n; i++) cin >> h[i], st.insert(h[i]);
	for (int i: st) m[i] = sz(m);
	for (int i = 1; i <= n; i++) h[i] = m[h[i]];
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		p[i] = p[i - 1] + (h[i] == 0);
		l[i] = (h[i] == 1 ? p[i - 1] : get(0, h[i] - 1));
		upd(h[i]);
	}
	fill(t, t + 4 * N, 0);
	for (int i = n; i >= 1; i--) {
		s[i] = s[i + 1] + (h[i] == 0);
		r[i] = (h[i] == 1 ? s[i + 1] : get(0, h[i] - 1));
		upd(h[i]);
	}
	for (int i = 1; i <= n; i++) ans += (l[i] * r[i]);
	cout << ans;
	cout << '\n';
}

bool testcases = 0;

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	int test = 1;
	if (testcases) cin >> test;
	for (int cs = 1; cs <= test; cs++) {
		solve();
	}
}

Compilation message

Mountains.cpp: In function 'void upd(int, int, int, int)':
Mountains.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
Mountains.cpp: In function 'll get(int, int, int, int, int)':
Mountains.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |  int tm = tl + tr >> 1;
      |           ~~~^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 429 ms 98228 KB Output is correct
3 Correct 418 ms 98136 KB Output is correct
4 Correct 398 ms 98116 KB Output is correct
5 Correct 419 ms 98092 KB Output is correct
6 Correct 407 ms 98084 KB Output is correct
7 Correct 424 ms 98120 KB Output is correct
8 Correct 412 ms 98112 KB Output is correct
9 Correct 245 ms 73252 KB Output is correct
10 Correct 237 ms 73304 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 40988 KB Output is correct
2 Correct 64 ms 40936 KB Output is correct
3 Correct 68 ms 41000 KB Output is correct
4 Correct 63 ms 41008 KB Output is correct
5 Correct 62 ms 41024 KB Output is correct
6 Correct 64 ms 41024 KB Output is correct
7 Correct 65 ms 41036 KB Output is correct
8 Correct 60 ms 41040 KB Output is correct
9 Correct 59 ms 40964 KB Output is correct
10 Correct 11 ms 31612 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 40988 KB Output is correct
2 Correct 64 ms 40936 KB Output is correct
3 Correct 68 ms 41000 KB Output is correct
4 Correct 63 ms 41008 KB Output is correct
5 Correct 62 ms 41024 KB Output is correct
6 Correct 64 ms 41024 KB Output is correct
7 Correct 65 ms 41036 KB Output is correct
8 Correct 60 ms 41040 KB Output is correct
9 Correct 59 ms 40964 KB Output is correct
10 Correct 11 ms 31612 KB Output is correct
11 Correct 154 ms 41004 KB Output is correct
12 Correct 154 ms 41012 KB Output is correct
13 Correct 154 ms 41032 KB Output is correct
14 Correct 158 ms 41112 KB Output is correct
15 Correct 156 ms 41036 KB Output is correct
16 Correct 156 ms 40956 KB Output is correct
17 Correct 153 ms 40988 KB Output is correct
18 Correct 107 ms 41024 KB Output is correct
19 Correct 106 ms 40968 KB Output is correct
20 Correct 12 ms 31552 KB Output is correct

Subtask #4
0 / 36.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 31700 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 64 ms 40988 KB Output is correct
2 Correct 64 ms 40936 KB Output is correct
3 Correct 68 ms 41000 KB Output is correct
4 Correct 63 ms 41008 KB Output is correct
5 Correct 62 ms 41024 KB Output is correct
6 Correct 64 ms 41024 KB Output is correct
7 Correct 65 ms 41036 KB Output is correct
8 Correct 60 ms 41040 KB Output is correct
9 Correct 59 ms 40964 KB Output is correct
10 Correct 11 ms 31612 KB Output is correct
11 Correct 154 ms 41004 KB Output is correct
12 Correct 154 ms 41012 KB Output is correct
13 Correct 154 ms 41032 KB Output is correct
14 Correct 158 ms 41112 KB Output is correct
15 Correct 156 ms 41036 KB Output is correct
16 Correct 156 ms 40956 KB Output is correct
17 Correct 153 ms 40988 KB Output is correct
18 Correct 107 ms 41024 KB Output is correct
19 Correct 106 ms 40968 KB Output is correct
20 Correct 12 ms 31552 KB Output is correct
21 Correct 387 ms 51452 KB Output is correct
22 Correct 409 ms 51360 KB Output is correct
23 Correct 382 ms 51532 KB Output is correct
24 Correct 385 ms 51404 KB Output is correct
25 Correct 373 ms 51332 KB Output is correct
26 Correct 383 ms 51448 KB Output is correct
27 Correct 437 ms 51404 KB Output is correct
28 Correct 208 ms 51404 KB Output is correct
29 Correct 206 ms 51360 KB Output is correct
30 Correct 12 ms 31572 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 429 ms 98228 KB Output is correct
3 Correct 418 ms 98136 KB Output is correct
4 Correct 398 ms 98116 KB Output is correct
5 Correct 419 ms 98092 KB Output is correct
6 Correct 407 ms 98084 KB Output is correct
7 Correct 424 ms 98120 KB Output is correct
8 Correct 412 ms 98112 KB Output is correct
9 Correct 245 ms 73252 KB Output is correct
10 Correct 237 ms 73304 KB Output is correct
11 Correct 64 ms 40988 KB Output is correct
12 Correct 64 ms 40936 KB Output is correct
13 Correct 68 ms 41000 KB Output is correct
14 Correct 63 ms 41008 KB Output is correct
15 Correct 62 ms 41024 KB Output is correct
16 Correct 64 ms 41024 KB Output is correct
17 Correct 65 ms 41036 KB Output is correct
18 Correct 60 ms 41040 KB Output is correct
19 Correct 59 ms 40964 KB Output is correct
20 Correct 11 ms 31612 KB Output is correct
21 Correct 154 ms 41004 KB Output is correct
22 Correct 154 ms 41012 KB Output is correct
23 Correct 154 ms 41032 KB Output is correct
24 Correct 158 ms 41112 KB Output is correct
25 Correct 156 ms 41036 KB Output is correct
26 Correct 156 ms 40956 KB Output is correct
27 Correct 153 ms 40988 KB Output is correct
28 Correct 107 ms 41024 KB Output is correct
29 Correct 106 ms 40968 KB Output is correct
30 Correct 12 ms 31552 KB Output is correct
31 Incorrect 12 ms 31700 KB Output isn't correct
32 Halted 0 ms 0 KB -