oj.uz

Submission #693326

# Submission time Handle Problem Language Result Execution time Memory
693326 2023-02-02T17:57:48 Z sudheerays123 Mountains (NOI20_mountains) C++17
100 / 100
 694 ms 112876 KB 
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define tc ll test;cin >> test;while(test--)
#define vi vector<ll>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define INF 1e18
#define MOD 1000000007
#define ff first
#define ss second
#define in >>
#define out <<
#define space << " " <<
#define spacef << " "
#define fo(i,a,b) for(ll i = a; i <= b; i++)
#define nextline out "\n"
#define print(x) for(auto i : x ) cout out i spacef
#define mmax(x,i) x = max(x,i)
#define mmin(x,i) x = min(x,i)
#define N 300005

vi a(N);
vi seg[4*N];

void build(ll node , ll l , ll r){

    if(l == r){
        seg[node].pb(a[l]);
        return;
    }

    ll mid = (l+r)/2;

    build(2*node,l,mid);
    build(2*node+1,mid+1,r);

    merge(seg[2*node].begin(),seg[2*node].end(),seg[2*node+1].begin(),seg[2*node+1].end(),back_inserter(seg[node]));
}

ll query(ll node , ll left , ll right , ll ql , ll qr , ll val){

    if(left > qr || right < ql) return 0;
    if(left >= ql && right <= qr){
        auto it = lower_bound(seg[node].begin(),seg[node].end(),val);
        return (seg[node].begin()-it);
    }

    ll mid = (left+right)/2;
    return query(2*node,left,mid,ql,qr,val) + query(2*node+1,mid+1,right,ql,qr,val);
}

int main() {
    
    fast;

    ll n;
    cin in n;

    fo(i,1,n) cin in a[i];

    build(1,1,n);

    ll ans = 0;
    fo(i,2,n-1) ans += query(1,1,n,1,i-1,a[i])*query(1,1,n,i+1,n,a[i]);

    cout out ans;

    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30804 KB Output is correct
2 Correct 336 ms 112748 KB Output is correct
3 Correct 331 ms 112824 KB Output is correct
4 Correct 331 ms 112864 KB Output is correct
5 Correct 325 ms 112876 KB Output is correct
6 Correct 324 ms 112856 KB Output is correct
7 Correct 334 ms 112860 KB Output is correct
8 Correct 324 ms 112864 KB Output is correct
9 Correct 331 ms 112860 KB Output is correct
10 Correct 334 ms 112812 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 107916 KB Output is correct
2 Correct 325 ms 107796 KB Output is correct
3 Correct 320 ms 107816 KB Output is correct
4 Correct 321 ms 107908 KB Output is correct
5 Correct 314 ms 107840 KB Output is correct
6 Correct 332 ms 107816 KB Output is correct
7 Correct 311 ms 107872 KB Output is correct
8 Correct 292 ms 107884 KB Output is correct
9 Correct 284 ms 107900 KB Output is correct
10 Correct 16 ms 30808 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 107916 KB Output is correct
2 Correct 325 ms 107796 KB Output is correct
3 Correct 320 ms 107816 KB Output is correct
4 Correct 321 ms 107908 KB Output is correct
5 Correct 314 ms 107840 KB Output is correct
6 Correct 332 ms 107816 KB Output is correct
7 Correct 311 ms 107872 KB Output is correct
8 Correct 292 ms 107884 KB Output is correct
9 Correct 284 ms 107900 KB Output is correct
10 Correct 16 ms 30808 KB Output is correct
11 Correct 569 ms 108096 KB Output is correct
12 Correct 575 ms 108112 KB Output is correct
13 Correct 556 ms 108140 KB Output is correct
14 Correct 591 ms 108092 KB Output is correct
15 Correct 573 ms 108144 KB Output is correct
16 Correct 559 ms 108136 KB Output is correct
17 Correct 580 ms 108180 KB Output is correct
18 Correct 299 ms 108140 KB Output is correct
19 Correct 292 ms 108112 KB Output is correct
20 Correct 15 ms 30804 KB Output is correct

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30868 KB Output is correct
2 Correct 15 ms 30932 KB Output is correct
3 Correct 16 ms 30916 KB Output is correct
4 Correct 17 ms 30912 KB Output is correct
5 Correct 16 ms 30940 KB Output is correct
6 Correct 17 ms 30932 KB Output is correct
7 Correct 16 ms 30852 KB Output is correct
8 Correct 16 ms 30828 KB Output is correct
9 Correct 15 ms 30876 KB Output is correct
10 Correct 15 ms 30804 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30868 KB Output is correct
2 Correct 15 ms 30932 KB Output is correct
3 Correct 16 ms 30916 KB Output is correct
4 Correct 17 ms 30912 KB Output is correct
5 Correct 16 ms 30940 KB Output is correct
6 Correct 17 ms 30932 KB Output is correct
7 Correct 16 ms 30852 KB Output is correct
8 Correct 16 ms 30828 KB Output is correct
9 Correct 15 ms 30876 KB Output is correct
10 Correct 15 ms 30804 KB Output is correct
11 Correct 28 ms 33128 KB Output is correct
12 Correct 28 ms 33084 KB Output is correct
13 Correct 29 ms 33148 KB Output is correct
14 Correct 28 ms 33132 KB Output is correct
15 Correct 28 ms 33164 KB Output is correct
16 Correct 33 ms 33144 KB Output is correct
17 Correct 28 ms 33132 KB Output is correct
18 Correct 29 ms 33108 KB Output is correct
19 Correct 28 ms 32896 KB Output is correct
20 Correct 15 ms 30804 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 107916 KB Output is correct
2 Correct 325 ms 107796 KB Output is correct
3 Correct 320 ms 107816 KB Output is correct
4 Correct 321 ms 107908 KB Output is correct
5 Correct 314 ms 107840 KB Output is correct
6 Correct 332 ms 107816 KB Output is correct
7 Correct 311 ms 107872 KB Output is correct
8 Correct 292 ms 107884 KB Output is correct
9 Correct 284 ms 107900 KB Output is correct
10 Correct 16 ms 30808 KB Output is correct
11 Correct 569 ms 108096 KB Output is correct
12 Correct 575 ms 108112 KB Output is correct
13 Correct 556 ms 108140 KB Output is correct
14 Correct 591 ms 108092 KB Output is correct
15 Correct 573 ms 108144 KB Output is correct
16 Correct 559 ms 108136 KB Output is correct
17 Correct 580 ms 108180 KB Output is correct
18 Correct 299 ms 108140 KB Output is correct
19 Correct 292 ms 108112 KB Output is correct
20 Correct 15 ms 30804 KB Output is correct
21 Correct 658 ms 108960 KB Output is correct
22 Correct 646 ms 109004 KB Output is correct
23 Correct 640 ms 109036 KB Output is correct
24 Correct 655 ms 108988 KB Output is correct
25 Correct 652 ms 108996 KB Output is correct
26 Correct 654 ms 108988 KB Output is correct
27 Correct 653 ms 109052 KB Output is correct
28 Correct 306 ms 109104 KB Output is correct
29 Correct 305 ms 109064 KB Output is correct
30 Correct 15 ms 30804 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30804 KB Output is correct
2 Correct 336 ms 112748 KB Output is correct
3 Correct 331 ms 112824 KB Output is correct
4 Correct 331 ms 112864 KB Output is correct
5 Correct 325 ms 112876 KB Output is correct
6 Correct 324 ms 112856 KB Output is correct
7 Correct 334 ms 112860 KB Output is correct
8 Correct 324 ms 112864 KB Output is correct
9 Correct 331 ms 112860 KB Output is correct
10 Correct 334 ms 112812 KB Output is correct
11 Correct 325 ms 107916 KB Output is correct
12 Correct 325 ms 107796 KB Output is correct
13 Correct 320 ms 107816 KB Output is correct
14 Correct 321 ms 107908 KB Output is correct
15 Correct 314 ms 107840 KB Output is correct
16 Correct 332 ms 107816 KB Output is correct
17 Correct 311 ms 107872 KB Output is correct
18 Correct 292 ms 107884 KB Output is correct
19 Correct 284 ms 107900 KB Output is correct
20 Correct 16 ms 30808 KB Output is correct
21 Correct 569 ms 108096 KB Output is correct
22 Correct 575 ms 108112 KB Output is correct
23 Correct 556 ms 108140 KB Output is correct
24 Correct 591 ms 108092 KB Output is correct
25 Correct 573 ms 108144 KB Output is correct
26 Correct 559 ms 108136 KB Output is correct
27 Correct 580 ms 108180 KB Output is correct
28 Correct 299 ms 108140 KB Output is correct
29 Correct 292 ms 108112 KB Output is correct
30 Correct 15 ms 30804 KB Output is correct
31 Correct 15 ms 30868 KB Output is correct
32 Correct 15 ms 30932 KB Output is correct
33 Correct 16 ms 30916 KB Output is correct
34 Correct 17 ms 30912 KB Output is correct
35 Correct 16 ms 30940 KB Output is correct
36 Correct 17 ms 30932 KB Output is correct
37 Correct 16 ms 30852 KB Output is correct
38 Correct 16 ms 30828 KB Output is correct
39 Correct 15 ms 30876 KB Output is correct
40 Correct 15 ms 30804 KB Output is correct
41 Correct 28 ms 33128 KB Output is correct
42 Correct 28 ms 33084 KB Output is correct
43 Correct 29 ms 33148 KB Output is correct
44 Correct 28 ms 33132 KB Output is correct
45 Correct 28 ms 33164 KB Output is correct
46 Correct 33 ms 33144 KB Output is correct
47 Correct 28 ms 33132 KB Output is correct
48 Correct 29 ms 33108 KB Output is correct
49 Correct 28 ms 32896 KB Output is correct
50 Correct 15 ms 30804 KB Output is correct
51 Correct 658 ms 108960 KB Output is correct
52 Correct 646 ms 109004 KB Output is correct
53 Correct 640 ms 109036 KB Output is correct
54 Correct 655 ms 108988 KB Output is correct
55 Correct 652 ms 108996 KB Output is correct
56 Correct 654 ms 108988 KB Output is correct
57 Correct 653 ms 109052 KB Output is correct
58 Correct 306 ms 109104 KB Output is correct
59 Correct 305 ms 109064 KB Output is correct
60 Correct 15 ms 30804 KB Output is correct
61 Correct 689 ms 112864 KB Output is correct
62 Correct 674 ms 112832 KB Output is correct
63 Correct 694 ms 112764 KB Output is correct
64 Correct 677 ms 112860 KB Output is correct
65 Correct 668 ms 112820 KB Output is correct
66 Correct 662 ms 112828 KB Output is correct
67 Correct 666 ms 112828 KB Output is correct
68 Correct 671 ms 112828 KB Output is correct
69 Correct 679 ms 109116 KB Output is correct
70 Correct 16 ms 30832 KB Output is correct