oj.uz

Submission #563554

# Submission time Handle Problem Language Result Execution time Memory
563554 2022-05-17T13:21:08 Z Cookie Mountains (NOI20_mountains) C++14
24 / 100
 223 ms 20936 KB 
#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
int n;
int a[300000];
int b[300000];
vt<int>tree; vt<int>tr;
int gett(int nd, int l, int r, int q_l, int q_r){
	if(q_l > r || q_r < l)return(0);
	if(q_l <= l && q_r >= r)return(tree[nd]);
	int mid = (l + r) >> 1;
	return(gett((nd << 1), l, mid, q_l, q_r) + gett((nd << 1) + 1, mid + 1, r, q_l, q_r));
}
int get(int nd, int l, int r, int q_l, int q_r){
	if(q_l > r || q_r < l)return(0);
	if(q_l <= l && q_r >= r)return(tr[nd]);
	int mid = (l + r) >> 1;
	return(get((nd << 1), l, mid, q_l, q_r) + get((nd << 1) + 1, mid + 1, r, q_l, q_r));
}
void upd(int p){
	tree[p + n]++;
	for(int i = (p + n) >> 1; i >= 1; i = i >> 1){
		tree[i]++;
	}
}
void updd(int p, ll v){
	tr[p + n] += v;
	for(int i = (p + n) >> 1; i >= 1; i = i >> 1){
		tr[i] += v;
	}
}

int main(){
    LIFESUCKS;
    cin >> n;
    int cr = n;
    for(int i = 0; i < n; i++){
        cin >> a[i]; b[i] = a[i];
    }
    sort(b, b + n);
    for(int i = 0; i < n; i++){
        a[i] = lower_bound(b, b + n, a[i]) - b;
    }
	while(__builtin_popcount(n) != 1)n++;
	
	tree.resize(2 * n, 0);
	ll left[n] = {0};
	for(int i = cr - 1; i >= 0; i--){
	    left[i] = gett(1, 0, n - 1, 0, a[i] - 1);
	    upd(a[i]);
	}
	ll right[n] = {0};
	tr.resize(2 * n, 0);
	for(int i = 0; i < cr; i++ ){
	    right[i] = get(1, 0, n - 1, 0, a[i] - 1);
	    updd(a[i], 1);
	}
	ll ans = 0;
	for(int i = 1; i < n - 1; i++){
	    ans += (right[i] * left[i]);
	}
	cout << ans;
}

Compilation message

Mountains.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("O3")
      | 
Mountains.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 50 ms 19120 KB Output is correct
3 Correct 50 ms 19020 KB Output is correct
4 Correct 50 ms 19132 KB Output is correct
5 Correct 59 ms 19080 KB Output is correct
6 Correct 51 ms 19148 KB Output is correct
7 Correct 49 ms 19120 KB Output is correct
8 Correct 51 ms 19132 KB Output is correct
9 Correct 51 ms 19132 KB Output is correct
10 Correct 50 ms 19128 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 19628 KB Output is correct
2 Correct 83 ms 19656 KB Output is correct
3 Correct 65 ms 19680 KB Output is correct
4 Correct 86 ms 19656 KB Output is correct
5 Correct 78 ms 19628 KB Output is correct
6 Correct 77 ms 19624 KB Output is correct
7 Correct 84 ms 19676 KB Output is correct
8 Correct 72 ms 19660 KB Output is correct
9 Correct 74 ms 19688 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 19628 KB Output is correct
2 Correct 83 ms 19656 KB Output is correct
3 Correct 65 ms 19680 KB Output is correct
4 Correct 86 ms 19656 KB Output is correct
5 Correct 78 ms 19628 KB Output is correct
6 Correct 77 ms 19624 KB Output is correct
7 Correct 84 ms 19676 KB Output is correct
8 Correct 72 ms 19660 KB Output is correct
9 Correct 74 ms 19688 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 148 ms 20040 KB Output is correct
12 Correct 151 ms 20044 KB Output is correct
13 Correct 149 ms 19932 KB Output is correct
14 Correct 150 ms 19888 KB Output is correct
15 Correct 148 ms 19932 KB Output is correct
16 Correct 149 ms 19892 KB Output is correct
17 Correct 149 ms 19940 KB Output is correct
18 Correct 88 ms 19940 KB Output is correct
19 Correct 87 ms 19940 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #4
0 / 36.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 79 ms 19628 KB Output is correct
2 Correct 83 ms 19656 KB Output is correct
3 Correct 65 ms 19680 KB Output is correct
4 Correct 86 ms 19656 KB Output is correct
5 Correct 78 ms 19628 KB Output is correct
6 Correct 77 ms 19624 KB Output is correct
7 Correct 84 ms 19676 KB Output is correct
8 Correct 72 ms 19660 KB Output is correct
9 Correct 74 ms 19688 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 148 ms 20040 KB Output is correct
12 Correct 151 ms 20044 KB Output is correct
13 Correct 149 ms 19932 KB Output is correct
14 Correct 150 ms 19888 KB Output is correct
15 Correct 148 ms 19932 KB Output is correct
16 Correct 149 ms 19892 KB Output is correct
17 Correct 149 ms 19940 KB Output is correct
18 Correct 88 ms 19940 KB Output is correct
19 Correct 87 ms 19940 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 223 ms 20824 KB Output is correct
22 Correct 207 ms 20936 KB Output is correct
23 Correct 206 ms 20924 KB Output is correct
24 Correct 205 ms 20768 KB Output is correct
25 Correct 205 ms 20764 KB Output is correct
26 Correct 202 ms 20816 KB Output is correct
27 Correct 213 ms 20812 KB Output is correct
28 Correct 119 ms 20764 KB Output is correct
29 Correct 115 ms 20880 KB Output is correct
30 Correct 0 ms 212 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 50 ms 19120 KB Output is correct
3 Correct 50 ms 19020 KB Output is correct
4 Correct 50 ms 19132 KB Output is correct
5 Correct 59 ms 19080 KB Output is correct
6 Correct 51 ms 19148 KB Output is correct
7 Correct 49 ms 19120 KB Output is correct
8 Correct 51 ms 19132 KB Output is correct
9 Correct 51 ms 19132 KB Output is correct
10 Correct 50 ms 19128 KB Output is correct
11 Correct 79 ms 19628 KB Output is correct
12 Correct 83 ms 19656 KB Output is correct
13 Correct 65 ms 19680 KB Output is correct
14 Correct 86 ms 19656 KB Output is correct
15 Correct 78 ms 19628 KB Output is correct
16 Correct 77 ms 19624 KB Output is correct
17 Correct 84 ms 19676 KB Output is correct
18 Correct 72 ms 19660 KB Output is correct
19 Correct 74 ms 19688 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 148 ms 20040 KB Output is correct
22 Correct 151 ms 20044 KB Output is correct
23 Correct 149 ms 19932 KB Output is correct
24 Correct 150 ms 19888 KB Output is correct
25 Correct 148 ms 19932 KB Output is correct
26 Correct 149 ms 19892 KB Output is correct
27 Correct 149 ms 19940 KB Output is correct
28 Correct 88 ms 19940 KB Output is correct
29 Correct 87 ms 19940 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Incorrect 1 ms 340 KB Output isn't correct
32 Halted 0 ms 0 KB -