답안 #1092253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1092253	2024-09-23T16:01:09 Z	whoknow	Mountains (NOI20_mountains)	C++17	24 / 100	112 ms	3972 KB

Mountains

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define N 300005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
int n;
int a[N];
namespace sub1
{
	ll res;
	int bit[N][2];
	void upd(int id,int v,int k)
	{
		for(id;id<=n;id+=(id&(-id)))
			bit[id][k]+=v;
	}
	int get(int id,int k)
	{
		int t=0;
		for(id;id>0;id-=((id&(-id))))
			t+=bit[id][k];
		return t;
	}
	void compress()
	{
		vector<int>v;
		for(int i=1;i<=n;i++)
			v.push_back(a[i]);
		sort(v.begin(),v.end());
		v.resize(unique(v.begin(),v.end())-v.begin());
		for(int i=1;i<=n;i++)
			a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
	}
	void solve()
	{
		compress();
		for(int i=2;i<=n;i++)
			upd(a[i],1,1);
		upd(a[1],1,0);
		for(int i=2;i<n;i++)
		{
			res+=1LL*get(a[i]-1,0)*get(a[i]-1,1);
			upd(a[i],-1,1);
			upd(a[i],1,0);
		}
		cout<<res;
	}
}
main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sub1::solve();
}

Compilation message

Mountains.cpp: In function 'void sub1::upd(int, int, int)':
Mountains.cpp:19:7: warning: statement has no effect [-Wunused-value]
   19 |   for(id;id<=n;id+=(id&(-id)))
      |       ^~
Mountains.cpp: In function 'int sub1::get(int, int)':
Mountains.cpp:25:7: warning: statement has no effect [-Wunused-value]
   25 |   for(id;id>0;id-=((id&(-id))))
      |       ^~
Mountains.cpp: At global scope:
Mountains.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main()
      | ^~~~

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	55 ms	3648 KB	Output is correct
3	Correct	56 ms	3820 KB	Output is correct
4	Correct	56 ms	3644 KB	Output is correct
5	Correct	54 ms	3824 KB	Output is correct
6	Correct	49 ms	2772 KB	Output is correct
7	Correct	43 ms	2768 KB	Output is correct
8	Correct	51 ms	2816 KB	Output is correct
9	Correct	53 ms	3660 KB	Output is correct
10	Correct	56 ms	3648 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	80 ms	3796 KB	Output is correct
2	Correct	71 ms	3820 KB	Output is correct
3	Correct	58 ms	3656 KB	Output is correct
4	Correct	71 ms	3796 KB	Output is correct
5	Correct	62 ms	3796 KB	Output is correct
6	Correct	61 ms	3796 KB	Output is correct
7	Correct	68 ms	3800 KB	Output is correct
8	Correct	61 ms	3796 KB	Output is correct
9	Correct	57 ms	3800 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	80 ms	3796 KB	Output is correct
2	Correct	71 ms	3820 KB	Output is correct
3	Correct	58 ms	3656 KB	Output is correct
4	Correct	71 ms	3796 KB	Output is correct
5	Correct	62 ms	3796 KB	Output is correct
6	Correct	61 ms	3796 KB	Output is correct
7	Correct	68 ms	3800 KB	Output is correct
8	Correct	61 ms	3796 KB	Output is correct
9	Correct	57 ms	3800 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	68 ms	3840 KB	Output is correct
12	Correct	71 ms	3796 KB	Output is correct
13	Correct	61 ms	3800 KB	Output is correct
14	Correct	57 ms	3600 KB	Output is correct
15	Correct	75 ms	3788 KB	Output is correct
16	Correct	58 ms	3800 KB	Output is correct
17	Correct	74 ms	3796 KB	Output is correct
18	Correct	44 ms	3796 KB	Output is correct
19	Correct	50 ms	3800 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct

Subtask #4
0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	344 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	344 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	80 ms	3796 KB	Output is correct
2	Correct	71 ms	3820 KB	Output is correct
3	Correct	58 ms	3656 KB	Output is correct
4	Correct	71 ms	3796 KB	Output is correct
5	Correct	62 ms	3796 KB	Output is correct
6	Correct	61 ms	3796 KB	Output is correct
7	Correct	68 ms	3800 KB	Output is correct
8	Correct	61 ms	3796 KB	Output is correct
9	Correct	57 ms	3800 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	68 ms	3840 KB	Output is correct
12	Correct	71 ms	3796 KB	Output is correct
13	Correct	61 ms	3800 KB	Output is correct
14	Correct	57 ms	3600 KB	Output is correct
15	Correct	75 ms	3788 KB	Output is correct
16	Correct	58 ms	3800 KB	Output is correct
17	Correct	74 ms	3796 KB	Output is correct
18	Correct	44 ms	3796 KB	Output is correct
19	Correct	50 ms	3800 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	112 ms	3892 KB	Output is correct
22	Correct	91 ms	3800 KB	Output is correct
23	Correct	98 ms	3800 KB	Output is correct
24	Correct	95 ms	3796 KB	Output is correct
25	Correct	109 ms	3972 KB	Output is correct
26	Correct	107 ms	3824 KB	Output is correct
27	Correct	88 ms	3796 KB	Output is correct
28	Correct	48 ms	3800 KB	Output is correct
29	Correct	45 ms	3800 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct

Subtask #7
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	55 ms	3648 KB	Output is correct
3	Correct	56 ms	3820 KB	Output is correct
4	Correct	56 ms	3644 KB	Output is correct
5	Correct	54 ms	3824 KB	Output is correct
6	Correct	49 ms	2772 KB	Output is correct
7	Correct	43 ms	2768 KB	Output is correct
8	Correct	51 ms	2816 KB	Output is correct
9	Correct	53 ms	3660 KB	Output is correct
10	Correct	56 ms	3648 KB	Output is correct
11	Correct	80 ms	3796 KB	Output is correct
12	Correct	71 ms	3820 KB	Output is correct
13	Correct	58 ms	3656 KB	Output is correct
14	Correct	71 ms	3796 KB	Output is correct
15	Correct	62 ms	3796 KB	Output is correct
16	Correct	61 ms	3796 KB	Output is correct
17	Correct	68 ms	3800 KB	Output is correct
18	Correct	61 ms	3796 KB	Output is correct
19	Correct	57 ms	3800 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	68 ms	3840 KB	Output is correct
22	Correct	71 ms	3796 KB	Output is correct
23	Correct	61 ms	3800 KB	Output is correct
24	Correct	57 ms	3600 KB	Output is correct
25	Correct	75 ms	3788 KB	Output is correct
26	Correct	58 ms	3800 KB	Output is correct
27	Correct	74 ms	3796 KB	Output is correct
28	Correct	44 ms	3796 KB	Output is correct
29	Correct	50 ms	3800 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Incorrect	0 ms	344 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

답안 #1092253

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 4.0 / 4.0

Subtask #3 9.0 / 9.0

Subtask #4 0 / 36.0

Subtask #5 0 / 28.0

Subtask #6 9.0 / 9.0

Subtask #7 0 / 12.0

Subtask #1
2.0 / 2.0

Subtask #2
4.0 / 4.0

Subtask #3
9.0 / 9.0

Subtask #4
0 / 36.0

Subtask #5
0 / 28.0

Subtask #6
9.0 / 9.0

Subtask #7
0 / 12.0