Submission #335605

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
335605	2020-12-13T09:11:24 Z	beepbeepsheep	Mountains (NOI20_mountains)	C++17	100 / 100	887 ms	117724 KB

Mountains

#include <bits/stdc++.h>

using namespace std;
#define ll long long
vector<ll> tree[1200020];
const ll inf=2e9;
ll arr[300005];
void build(ll node,ll s,ll e){
    if (s==e){
        tree[node].emplace_back(arr[s]);
        return;
    }
    ll m=(s+e)/2;
    ll left=node<<1;
    ll right=left|1;
    build(left,s,m);
    build(right,m+1,e);
    merge(tree[left].begin(),tree[left].end(),tree[right].begin(),tree[right].end(),back_inserter(tree[node]));
}
ll query(ll node,ll l,ll r,ll i,ll j,ll k){
    if (i>r||j<l) return 0;
    if (i<=l && r<=j) return lower_bound(tree[node].begin(),tree[node].end(),k)-tree[node].begin();
    ll mid=(l+r)/2;
    ll left=node<<1;
    ll right=left|1;
    return query(left,l,mid,i,j,k)+query(right,mid+1,r,i,j,k);

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n;
    cin>>n;
    pair<ll,ll> num[n];
    for (ll i=0;i<n;i++){
        cin>>num[i].first;
        arr[i]=num[i].first;
        num[i].second=i;
    }
    ll a,b;
    ll ans=0;
    build(1,0,n-1);
    for (ll i=0;i<n;i++){
        a=query(1,0,n-1,num[i].second,n-1,num[i].first);
        b=query(1,0,n-1,0,num[i].second,num[i].first);
        ans+=a*b;
    }
    cout<<ans;
	return 0;
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	28524 KB	Output is correct
2	Correct	456 ms	117596 KB	Output is correct
3	Correct	453 ms	117596 KB	Output is correct
4	Correct	479 ms	117724 KB	Output is correct
5	Correct	483 ms	117596 KB	Output is correct
6	Correct	456 ms	117596 KB	Output is correct
7	Correct	449 ms	117596 KB	Output is correct
8	Correct	453 ms	117724 KB	Output is correct
9	Correct	476 ms	117712 KB	Output is correct
10	Correct	474 ms	117596 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	479 ms	112476 KB	Output is correct
2	Correct	442 ms	112732 KB	Output is correct
3	Correct	446 ms	112604 KB	Output is correct
4	Correct	447 ms	112604 KB	Output is correct
5	Correct	445 ms	112604 KB	Output is correct
6	Correct	450 ms	112604 KB	Output is correct
7	Correct	445 ms	112604 KB	Output is correct
8	Correct	438 ms	112604 KB	Output is correct
9	Correct	432 ms	112604 KB	Output is correct
10	Correct	19 ms	28524 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	479 ms	112476 KB	Output is correct
2	Correct	442 ms	112732 KB	Output is correct
3	Correct	446 ms	112604 KB	Output is correct
4	Correct	447 ms	112604 KB	Output is correct
5	Correct	445 ms	112604 KB	Output is correct
6	Correct	450 ms	112604 KB	Output is correct
7	Correct	445 ms	112604 KB	Output is correct
8	Correct	438 ms	112604 KB	Output is correct
9	Correct	432 ms	112604 KB	Output is correct
10	Correct	19 ms	28524 KB	Output is correct
11	Correct	718 ms	112860 KB	Output is correct
12	Correct	715 ms	112860 KB	Output is correct
13	Correct	751 ms	112860 KB	Output is correct
14	Correct	715 ms	112860 KB	Output is correct
15	Correct	702 ms	112856 KB	Output is correct
16	Correct	692 ms	112860 KB	Output is correct
17	Correct	722 ms	112860 KB	Output is correct
18	Correct	426 ms	112872 KB	Output is correct
19	Correct	430 ms	112860 KB	Output is correct
20	Correct	21 ms	28524 KB	Output is correct

Subtask #4
36.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	28652 KB	Output is correct
2	Correct	23 ms	28652 KB	Output is correct
3	Correct	20 ms	28652 KB	Output is correct
4	Correct	20 ms	28652 KB	Output is correct
5	Correct	19 ms	28652 KB	Output is correct
6	Correct	22 ms	28652 KB	Output is correct
7	Correct	22 ms	28652 KB	Output is correct
8	Correct	23 ms	28652 KB	Output is correct
9	Correct	20 ms	28652 KB	Output is correct
10	Correct	21 ms	28524 KB	Output is correct

Subtask #5
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	28652 KB	Output is correct
2	Correct	23 ms	28652 KB	Output is correct
3	Correct	20 ms	28652 KB	Output is correct
4	Correct	20 ms	28652 KB	Output is correct
5	Correct	19 ms	28652 KB	Output is correct
6	Correct	22 ms	28652 KB	Output is correct
7	Correct	22 ms	28652 KB	Output is correct
8	Correct	23 ms	28652 KB	Output is correct
9	Correct	20 ms	28652 KB	Output is correct
10	Correct	21 ms	28524 KB	Output is correct
11	Correct	72 ms	31084 KB	Output is correct
12	Correct	38 ms	31084 KB	Output is correct
13	Correct	44 ms	31084 KB	Output is correct
14	Correct	39 ms	31084 KB	Output is correct
15	Correct	40 ms	31084 KB	Output is correct
16	Correct	39 ms	31104 KB	Output is correct
17	Correct	41 ms	31084 KB	Output is correct
18	Correct	40 ms	31084 KB	Output is correct
19	Correct	37 ms	30956 KB	Output is correct
20	Correct	21 ms	28596 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	479 ms	112476 KB	Output is correct
2	Correct	442 ms	112732 KB	Output is correct
3	Correct	446 ms	112604 KB	Output is correct
4	Correct	447 ms	112604 KB	Output is correct
5	Correct	445 ms	112604 KB	Output is correct
6	Correct	450 ms	112604 KB	Output is correct
7	Correct	445 ms	112604 KB	Output is correct
8	Correct	438 ms	112604 KB	Output is correct
9	Correct	432 ms	112604 KB	Output is correct
10	Correct	19 ms	28524 KB	Output is correct
11	Correct	718 ms	112860 KB	Output is correct
12	Correct	715 ms	112860 KB	Output is correct
13	Correct	751 ms	112860 KB	Output is correct
14	Correct	715 ms	112860 KB	Output is correct
15	Correct	702 ms	112856 KB	Output is correct
16	Correct	692 ms	112860 KB	Output is correct
17	Correct	722 ms	112860 KB	Output is correct
18	Correct	426 ms	112872 KB	Output is correct
19	Correct	430 ms	112860 KB	Output is correct
20	Correct	21 ms	28524 KB	Output is correct
21	Correct	851 ms	113756 KB	Output is correct
22	Correct	837 ms	113940 KB	Output is correct
23	Correct	834 ms	113792 KB	Output is correct
24	Correct	834 ms	113808 KB	Output is correct
25	Correct	828 ms	113756 KB	Output is correct
26	Correct	844 ms	113884 KB	Output is correct
27	Correct	850 ms	113784 KB	Output is correct
28	Correct	440 ms	113840 KB	Output is correct
29	Correct	448 ms	113756 KB	Output is correct
30	Correct	20 ms	28524 KB	Output is correct

Subtask #7
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	28524 KB	Output is correct
2	Correct	456 ms	117596 KB	Output is correct
3	Correct	453 ms	117596 KB	Output is correct
4	Correct	479 ms	117724 KB	Output is correct
5	Correct	483 ms	117596 KB	Output is correct
6	Correct	456 ms	117596 KB	Output is correct
7	Correct	449 ms	117596 KB	Output is correct
8	Correct	453 ms	117724 KB	Output is correct
9	Correct	476 ms	117712 KB	Output is correct
10	Correct	474 ms	117596 KB	Output is correct
11	Correct	479 ms	112476 KB	Output is correct
12	Correct	442 ms	112732 KB	Output is correct
13	Correct	446 ms	112604 KB	Output is correct
14	Correct	447 ms	112604 KB	Output is correct
15	Correct	445 ms	112604 KB	Output is correct
16	Correct	450 ms	112604 KB	Output is correct
17	Correct	445 ms	112604 KB	Output is correct
18	Correct	438 ms	112604 KB	Output is correct
19	Correct	432 ms	112604 KB	Output is correct
20	Correct	19 ms	28524 KB	Output is correct
21	Correct	718 ms	112860 KB	Output is correct
22	Correct	715 ms	112860 KB	Output is correct
23	Correct	751 ms	112860 KB	Output is correct
24	Correct	715 ms	112860 KB	Output is correct
25	Correct	702 ms	112856 KB	Output is correct
26	Correct	692 ms	112860 KB	Output is correct
27	Correct	722 ms	112860 KB	Output is correct
28	Correct	426 ms	112872 KB	Output is correct
29	Correct	430 ms	112860 KB	Output is correct
30	Correct	21 ms	28524 KB	Output is correct
31	Correct	19 ms	28652 KB	Output is correct
32	Correct	23 ms	28652 KB	Output is correct
33	Correct	20 ms	28652 KB	Output is correct
34	Correct	20 ms	28652 KB	Output is correct
35	Correct	19 ms	28652 KB	Output is correct
36	Correct	22 ms	28652 KB	Output is correct
37	Correct	22 ms	28652 KB	Output is correct
38	Correct	23 ms	28652 KB	Output is correct
39	Correct	20 ms	28652 KB	Output is correct
40	Correct	21 ms	28524 KB	Output is correct
41	Correct	72 ms	31084 KB	Output is correct
42	Correct	38 ms	31084 KB	Output is correct
43	Correct	44 ms	31084 KB	Output is correct
44	Correct	39 ms	31084 KB	Output is correct
45	Correct	40 ms	31084 KB	Output is correct
46	Correct	39 ms	31104 KB	Output is correct
47	Correct	41 ms	31084 KB	Output is correct
48	Correct	40 ms	31084 KB	Output is correct
49	Correct	37 ms	30956 KB	Output is correct
50	Correct	21 ms	28596 KB	Output is correct
51	Correct	851 ms	113756 KB	Output is correct
52	Correct	837 ms	113940 KB	Output is correct
53	Correct	834 ms	113792 KB	Output is correct
54	Correct	834 ms	113808 KB	Output is correct
55	Correct	828 ms	113756 KB	Output is correct
56	Correct	844 ms	113884 KB	Output is correct
57	Correct	850 ms	113784 KB	Output is correct
58	Correct	440 ms	113840 KB	Output is correct
59	Correct	448 ms	113756 KB	Output is correct
60	Correct	20 ms	28524 KB	Output is correct
61	Correct	870 ms	117572 KB	Output is correct
62	Correct	887 ms	117608 KB	Output is correct
63	Correct	881 ms	117588 KB	Output is correct
64	Correct	849 ms	117644 KB	Output is correct
65	Correct	861 ms	117596 KB	Output is correct
66	Correct	872 ms	117612 KB	Output is correct
67	Correct	861 ms	117624 KB	Output is correct
68	Correct	870 ms	117584 KB	Output is correct
69	Correct	867 ms	113884 KB	Output is correct
70	Correct	21 ms	28524 KB	Output is correct

Submission #335605

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 4.0 / 4.0

Subtask #3 9.0 / 9.0

Subtask #4 36.0 / 36.0

Subtask #5 28.0 / 28.0

Subtask #6 9.0 / 9.0

Subtask #7 12.0 / 12.0

Subtask #1
2.0 / 2.0

Subtask #2
4.0 / 4.0

Subtask #3
9.0 / 9.0

Subtask #4
36.0 / 36.0

Subtask #5
28.0 / 28.0

Subtask #6
9.0 / 9.0

Subtask #7
12.0 / 12.0