답안 #642806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
642806	2022-09-20T14:44:24 Z	Codula	Mountains (NOI20_mountains)	C++17	100 / 100	901 ms	88296 KB

Mountains

//IOI 2023 I am coming.
 
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define int int64_t
#define pb push_back
#define deb(x) cerr<<"("<<#x<<"="<<x<<','<<__LINE__<<")"<<endl; 
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
 
int32_t main(){
	fast;
	int n;
	cin>>n;
	vector<int>a(n);
	for(int i=0;i<n;++i){
		cin>>a[i];
	}
	ordered_set o1,o2;
	//~ map<int,int>mp;
	vector<int>pref(3e5+1),pref2(3e5+1);
	map<int,int>mp,mp2;
	for(int i=0;i<n;++i){
		int dx=o1.order_of_key({a[i],i})-mp[a[i]];
		pref[i]=dx;
		o1.insert({a[i],i});
		mp[a[i]]+=1;
	}
	//~ map<int,int>mp2;
	for(int i=n-1;i>=0;--i){
		int dx=o2.order_of_key({a[i],-i})-mp2[a[i]];
		pref2[i]=dx;
		o2.insert({a[i],-i});
		mp2[a[i]]+=1;
	}
	int ans=0;
	for(int i=0;i<n;++i){
		//~ deb(pref[i]);
		//~ deb(pref2[i]);
		ans+=(pref[i]*pref2[i]);
	}
	cout<<ans<<"\n";
    return 0;
}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	725 ms	88064 KB	Output is correct
3	Correct	742 ms	88012 KB	Output is correct
4	Correct	851 ms	88024 KB	Output is correct
5	Correct	860 ms	88152 KB	Output is correct
6	Correct	753 ms	88012 KB	Output is correct
7	Correct	877 ms	87940 KB	Output is correct
8	Correct	802 ms	88096 KB	Output is correct
9	Correct	386 ms	69932 KB	Output is correct
10	Correct	390 ms	70120 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	298 ms	45612 KB	Output is correct
2	Correct	288 ms	45516 KB	Output is correct
3	Correct	282 ms	45476 KB	Output is correct
4	Correct	295 ms	45448 KB	Output is correct
5	Correct	275 ms	45516 KB	Output is correct
6	Correct	319 ms	45552 KB	Output is correct
7	Correct	272 ms	45412 KB	Output is correct
8	Correct	482 ms	45408 KB	Output is correct
9	Correct	465 ms	45408 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	298 ms	45612 KB	Output is correct
2	Correct	288 ms	45516 KB	Output is correct
3	Correct	282 ms	45476 KB	Output is correct
4	Correct	295 ms	45448 KB	Output is correct
5	Correct	275 ms	45516 KB	Output is correct
6	Correct	319 ms	45552 KB	Output is correct
7	Correct	272 ms	45412 KB	Output is correct
8	Correct	482 ms	45408 KB	Output is correct
9	Correct	465 ms	45408 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	446 ms	45668 KB	Output is correct
12	Correct	436 ms	45748 KB	Output is correct
13	Correct	426 ms	45772 KB	Output is correct
14	Correct	437 ms	45776 KB	Output is correct
15	Correct	422 ms	45716 KB	Output is correct
16	Correct	479 ms	45744 KB	Output is correct
17	Correct	426 ms	45808 KB	Output is correct
18	Correct	320 ms	45756 KB	Output is correct
19	Correct	339 ms	45688 KB	Output is correct
20	Correct	2 ms	4948 KB	Output is correct

Subtask #4
36.0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	3 ms	5192 KB	Output is correct
3	Correct	2 ms	5076 KB	Output is correct
4	Correct	3 ms	5076 KB	Output is correct
5	Correct	3 ms	5076 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	3 ms	5076 KB	Output is correct
8	Correct	3 ms	5076 KB	Output is correct
9	Correct	2 ms	5076 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct

Subtask #5
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	3 ms	5192 KB	Output is correct
3	Correct	2 ms	5076 KB	Output is correct
4	Correct	3 ms	5076 KB	Output is correct
5	Correct	3 ms	5076 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	3 ms	5076 KB	Output is correct
8	Correct	3 ms	5076 KB	Output is correct
9	Correct	2 ms	5076 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	17 ms	7700 KB	Output is correct
12	Correct	17 ms	7676 KB	Output is correct
13	Correct	17 ms	7756 KB	Output is correct
14	Correct	17 ms	7756 KB	Output is correct
15	Correct	17 ms	7756 KB	Output is correct
16	Correct	18 ms	7764 KB	Output is correct
17	Correct	18 ms	7752 KB	Output is correct
18	Correct	17 ms	7064 KB	Output is correct
19	Correct	13 ms	6428 KB	Output is correct
20	Correct	2 ms	4948 KB	Output is correct

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	298 ms	45612 KB	Output is correct
2	Correct	288 ms	45516 KB	Output is correct
3	Correct	282 ms	45476 KB	Output is correct
4	Correct	295 ms	45448 KB	Output is correct
5	Correct	275 ms	45516 KB	Output is correct
6	Correct	319 ms	45552 KB	Output is correct
7	Correct	272 ms	45412 KB	Output is correct
8	Correct	482 ms	45408 KB	Output is correct
9	Correct	465 ms	45408 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	446 ms	45668 KB	Output is correct
12	Correct	436 ms	45748 KB	Output is correct
13	Correct	426 ms	45772 KB	Output is correct
14	Correct	437 ms	45776 KB	Output is correct
15	Correct	422 ms	45716 KB	Output is correct
16	Correct	479 ms	45744 KB	Output is correct
17	Correct	426 ms	45808 KB	Output is correct
18	Correct	320 ms	45756 KB	Output is correct
19	Correct	339 ms	45688 KB	Output is correct
20	Correct	2 ms	4948 KB	Output is correct
21	Correct	758 ms	58528 KB	Output is correct
22	Correct	767 ms	58592 KB	Output is correct
23	Correct	752 ms	58464 KB	Output is correct
24	Correct	786 ms	58752 KB	Output is correct
25	Correct	777 ms	58576 KB	Output is correct
26	Correct	776 ms	58684 KB	Output is correct
27	Correct	773 ms	58620 KB	Output is correct
28	Correct	335 ms	58468 KB	Output is correct
29	Correct	324 ms	58468 KB	Output is correct
30	Correct	2 ms	4928 KB	Output is correct

Subtask #7
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	725 ms	88064 KB	Output is correct
3	Correct	742 ms	88012 KB	Output is correct
4	Correct	851 ms	88024 KB	Output is correct
5	Correct	860 ms	88152 KB	Output is correct
6	Correct	753 ms	88012 KB	Output is correct
7	Correct	877 ms	87940 KB	Output is correct
8	Correct	802 ms	88096 KB	Output is correct
9	Correct	386 ms	69932 KB	Output is correct
10	Correct	390 ms	70120 KB	Output is correct
11	Correct	298 ms	45612 KB	Output is correct
12	Correct	288 ms	45516 KB	Output is correct
13	Correct	282 ms	45476 KB	Output is correct
14	Correct	295 ms	45448 KB	Output is correct
15	Correct	275 ms	45516 KB	Output is correct
16	Correct	319 ms	45552 KB	Output is correct
17	Correct	272 ms	45412 KB	Output is correct
18	Correct	482 ms	45408 KB	Output is correct
19	Correct	465 ms	45408 KB	Output is correct
20	Correct	2 ms	4948 KB	Output is correct
21	Correct	446 ms	45668 KB	Output is correct
22	Correct	436 ms	45748 KB	Output is correct
23	Correct	426 ms	45772 KB	Output is correct
24	Correct	437 ms	45776 KB	Output is correct
25	Correct	422 ms	45716 KB	Output is correct
26	Correct	479 ms	45744 KB	Output is correct
27	Correct	426 ms	45808 KB	Output is correct
28	Correct	320 ms	45756 KB	Output is correct
29	Correct	339 ms	45688 KB	Output is correct
30	Correct	2 ms	4948 KB	Output is correct
31	Correct	3 ms	5076 KB	Output is correct
32	Correct	3 ms	5192 KB	Output is correct
33	Correct	2 ms	5076 KB	Output is correct
34	Correct	3 ms	5076 KB	Output is correct
35	Correct	3 ms	5076 KB	Output is correct
36	Correct	3 ms	5076 KB	Output is correct
37	Correct	3 ms	5076 KB	Output is correct
38	Correct	3 ms	5076 KB	Output is correct
39	Correct	2 ms	5076 KB	Output is correct
40	Correct	2 ms	4948 KB	Output is correct
41	Correct	17 ms	7700 KB	Output is correct
42	Correct	17 ms	7676 KB	Output is correct
43	Correct	17 ms	7756 KB	Output is correct
44	Correct	17 ms	7756 KB	Output is correct
45	Correct	17 ms	7756 KB	Output is correct
46	Correct	18 ms	7764 KB	Output is correct
47	Correct	18 ms	7752 KB	Output is correct
48	Correct	17 ms	7064 KB	Output is correct
49	Correct	13 ms	6428 KB	Output is correct
50	Correct	2 ms	4948 KB	Output is correct
51	Correct	758 ms	58528 KB	Output is correct
52	Correct	767 ms	58592 KB	Output is correct
53	Correct	752 ms	58464 KB	Output is correct
54	Correct	786 ms	58752 KB	Output is correct
55	Correct	777 ms	58576 KB	Output is correct
56	Correct	776 ms	58684 KB	Output is correct
57	Correct	773 ms	58620 KB	Output is correct
58	Correct	335 ms	58468 KB	Output is correct
59	Correct	324 ms	58468 KB	Output is correct
60	Correct	2 ms	4928 KB	Output is correct
61	Correct	835 ms	88296 KB	Output is correct
62	Correct	828 ms	88036 KB	Output is correct
63	Correct	835 ms	87996 KB	Output is correct
64	Correct	840 ms	88092 KB	Output is correct
65	Correct	866 ms	88012 KB	Output is correct
66	Correct	845 ms	87952 KB	Output is correct
67	Correct	856 ms	88024 KB	Output is correct
68	Correct	901 ms	69956 KB	Output is correct
69	Correct	783 ms	62988 KB	Output is correct
70	Correct	2 ms	4948 KB	Output is correct

답안 #642806

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