답안 #224860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224860	2020-04-19T03:44:03 Z	bukanYohandi	Mountains (NOI20_mountains)	C++14	100 / 100	267 ms	33528 KB

Mountains

 	#include <bits/stdc++.h>

#define fs first
#define sc second
#define pb push_back
#define eb emplace_back

#define all(a) a.begin(),a.end()
#define lb(a,x) (lower_bound(all(a),x)-a.begin())
#define ub(a,x) (upper_bound(all(a),x)-a.begin())

#define rep(a,x,y) for(int a=(int)x;a<=(int)y;++a)
#define repd(a,x,y,d) for(int a=(int)x;a<=(int)y;a+=d)
#define res(a,x,y) for(int a=(int)x;a>=(int)y;--a)
#define resd(a,x,y,d) for(int a=(int)x;a>=(int)y;a-=d)

// Ordered Set, Ordered Multiset
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define o_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define o_multiset tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
// .order_of_key(x) -> Number of elements less than x
// * .find_by_order(k) -> Kth smallest element (0-based)
// .erase(x) -> Remove all elements equal to x

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using lint=long long;

mt19937 rng(time(NULL));

lint Power(lint A,lint B,lint C){
	if(!B) return 1LL;
	lint tmp=Power(A,B>>1,C);
	return tmp*tmp%C*(B&1?A:1)%C;
}

struct Q{lint L,R,Idx,X;};
struct Smth{lint Idx,Val;} Arr[333333];

int T,N;
lint Ans,Le,Ri;
lint Bit[333333],H[333333],Prefix[111][333333];
lint Jwb[666666];
Q Query[666666];

lint Sum(int Idx){
    lint Ret=0;
    for(;Idx>0;Idx-=Idx&-Idx) Ret+=Bit[Idx];
    return Ret;
}
void Upd(int Idx){for(;Idx<=N+5;Idx+=Idx&-Idx) Bit[Idx]++;}
bool Cmp(Q A,Q B){return A.X<B.X;}
bool Cmp2(Smth A,Smth B){return A.Val<B.Val;}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1;
//	cin>>T;
	rep(t,1,T){
        cin>>N;
        for(int i=1;i<=N;++i) cin>>H[i];
        for(int i=2;i<=N-1;++i){
            Query[2*i-1].L=1;
            Query[2*i-1].R=i-1;
            Query[2*i-1].Idx=2*i-1;
            Query[2*i-1].X=H[i];
            Query[2*i].L=i+1;
            Query[2*i].R=N;
            Query[2*i].Idx=2*i;
            Query[2*i].X=H[i];
        }
        for(int i=1;i<=N;++i){
            Arr[i].Idx=i;
            Arr[i].Val=H[i];
        }
        sort(Arr+1,Arr+N+1,Cmp2);
        sort(Query+3,Query+2*N-1,Cmp);
        int Cur=1;
        for(int i=3;i<=2*N-2;++i){
            for(;Arr[Cur].Val<Query[i].X&&Cur<=N;Cur++) Upd(Arr[Cur].Idx);
            Jwb[Query[i].Idx]=Sum(Query[i].R)-Sum(Query[i].L-1);
        }
        for(int i=2;i<=N-1;++i) Ans+=(lint)Jwb[2*i-1]*Jwb[2*i];
        cout<<Ans<<endl;
	}
	return 0;
}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	181 ms	33272 KB	Output is correct
3	Correct	190 ms	33272 KB	Output is correct
4	Correct	187 ms	33272 KB	Output is correct
5	Correct	185 ms	33272 KB	Output is correct
6	Correct	195 ms	33272 KB	Output is correct
7	Correct	185 ms	33272 KB	Output is correct
8	Correct	176 ms	33272 KB	Output is correct
9	Correct	178 ms	33272 KB	Output is correct
10	Correct	185 ms	33400 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	33272 KB	Output is correct
2	Correct	125 ms	33272 KB	Output is correct
3	Correct	127 ms	33528 KB	Output is correct
4	Correct	124 ms	33272 KB	Output is correct
5	Correct	125 ms	33276 KB	Output is correct
6	Correct	130 ms	33272 KB	Output is correct
7	Correct	131 ms	33272 KB	Output is correct
8	Correct	121 ms	32120 KB	Output is correct
9	Correct	128 ms	32120 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	33272 KB	Output is correct
2	Correct	125 ms	33272 KB	Output is correct
3	Correct	127 ms	33528 KB	Output is correct
4	Correct	124 ms	33272 KB	Output is correct
5	Correct	125 ms	33276 KB	Output is correct
6	Correct	130 ms	33272 KB	Output is correct
7	Correct	131 ms	33272 KB	Output is correct
8	Correct	121 ms	32120 KB	Output is correct
9	Correct	128 ms	32120 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	155 ms	33272 KB	Output is correct
12	Correct	159 ms	33400 KB	Output is correct
13	Correct	163 ms	33400 KB	Output is correct
14	Correct	154 ms	33272 KB	Output is correct
15	Correct	166 ms	33272 KB	Output is correct
16	Correct	160 ms	33272 KB	Output is correct
17	Correct	167 ms	33400 KB	Output is correct
18	Correct	121 ms	33276 KB	Output is correct
19	Correct	128 ms	33276 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct

Subtask #4
36.0 / 36.0

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

Subtask #5
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	640 KB	Output is correct
3	Correct	5 ms	512 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	11 ms	1536 KB	Output is correct
12	Correct	12 ms	1536 KB	Output is correct
13	Correct	12 ms	1536 KB	Output is correct
14	Correct	11 ms	1536 KB	Output is correct
15	Correct	12 ms	1536 KB	Output is correct
16	Correct	12 ms	1536 KB	Output is correct
17	Correct	11 ms	1536 KB	Output is correct
18	Correct	12 ms	1536 KB	Output is correct
19	Correct	9 ms	1536 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	33272 KB	Output is correct
2	Correct	125 ms	33272 KB	Output is correct
3	Correct	127 ms	33528 KB	Output is correct
4	Correct	124 ms	33272 KB	Output is correct
5	Correct	125 ms	33276 KB	Output is correct
6	Correct	130 ms	33272 KB	Output is correct
7	Correct	131 ms	33272 KB	Output is correct
8	Correct	121 ms	32120 KB	Output is correct
9	Correct	128 ms	32120 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	155 ms	33272 KB	Output is correct
12	Correct	159 ms	33400 KB	Output is correct
13	Correct	163 ms	33400 KB	Output is correct
14	Correct	154 ms	33272 KB	Output is correct
15	Correct	166 ms	33272 KB	Output is correct
16	Correct	160 ms	33272 KB	Output is correct
17	Correct	167 ms	33400 KB	Output is correct
18	Correct	121 ms	33276 KB	Output is correct
19	Correct	128 ms	33276 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	215 ms	33400 KB	Output is correct
22	Correct	212 ms	33248 KB	Output is correct
23	Correct	210 ms	33400 KB	Output is correct
24	Correct	216 ms	33272 KB	Output is correct
25	Correct	213 ms	33272 KB	Output is correct
26	Correct	213 ms	33400 KB	Output is correct
27	Correct	225 ms	33400 KB	Output is correct
28	Correct	146 ms	33272 KB	Output is correct
29	Correct	141 ms	33272 KB	Output is correct
30	Correct	5 ms	384 KB	Output is correct

Subtask #7
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	181 ms	33272 KB	Output is correct
3	Correct	190 ms	33272 KB	Output is correct
4	Correct	187 ms	33272 KB	Output is correct
5	Correct	185 ms	33272 KB	Output is correct
6	Correct	195 ms	33272 KB	Output is correct
7	Correct	185 ms	33272 KB	Output is correct
8	Correct	176 ms	33272 KB	Output is correct
9	Correct	178 ms	33272 KB	Output is correct
10	Correct	185 ms	33400 KB	Output is correct
11	Correct	129 ms	33272 KB	Output is correct
12	Correct	125 ms	33272 KB	Output is correct
13	Correct	127 ms	33528 KB	Output is correct
14	Correct	124 ms	33272 KB	Output is correct
15	Correct	125 ms	33276 KB	Output is correct
16	Correct	130 ms	33272 KB	Output is correct
17	Correct	131 ms	33272 KB	Output is correct
18	Correct	121 ms	32120 KB	Output is correct
19	Correct	128 ms	32120 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	155 ms	33272 KB	Output is correct
22	Correct	159 ms	33400 KB	Output is correct
23	Correct	163 ms	33400 KB	Output is correct
24	Correct	154 ms	33272 KB	Output is correct
25	Correct	166 ms	33272 KB	Output is correct
26	Correct	160 ms	33272 KB	Output is correct
27	Correct	167 ms	33400 KB	Output is correct
28	Correct	121 ms	33276 KB	Output is correct
29	Correct	128 ms	33276 KB	Output is correct
30	Correct	5 ms	384 KB	Output is correct
31	Correct	5 ms	384 KB	Output is correct
32	Correct	5 ms	640 KB	Output is correct
33	Correct	5 ms	512 KB	Output is correct
34	Correct	5 ms	384 KB	Output is correct
35	Correct	5 ms	384 KB	Output is correct
36	Correct	5 ms	384 KB	Output is correct
37	Correct	5 ms	384 KB	Output is correct
38	Correct	5 ms	384 KB	Output is correct
39	Correct	5 ms	384 KB	Output is correct
40	Correct	5 ms	384 KB	Output is correct
41	Correct	11 ms	1536 KB	Output is correct
42	Correct	12 ms	1536 KB	Output is correct
43	Correct	12 ms	1536 KB	Output is correct
44	Correct	11 ms	1536 KB	Output is correct
45	Correct	12 ms	1536 KB	Output is correct
46	Correct	12 ms	1536 KB	Output is correct
47	Correct	11 ms	1536 KB	Output is correct
48	Correct	12 ms	1536 KB	Output is correct
49	Correct	9 ms	1536 KB	Output is correct
50	Correct	5 ms	384 KB	Output is correct
51	Correct	215 ms	33400 KB	Output is correct
52	Correct	212 ms	33248 KB	Output is correct
53	Correct	210 ms	33400 KB	Output is correct
54	Correct	216 ms	33272 KB	Output is correct
55	Correct	213 ms	33272 KB	Output is correct
56	Correct	213 ms	33400 KB	Output is correct
57	Correct	225 ms	33400 KB	Output is correct
58	Correct	146 ms	33272 KB	Output is correct
59	Correct	141 ms	33272 KB	Output is correct
60	Correct	5 ms	384 KB	Output is correct
61	Correct	253 ms	33276 KB	Output is correct
62	Correct	254 ms	33272 KB	Output is correct
63	Correct	254 ms	33272 KB	Output is correct
64	Correct	258 ms	33272 KB	Output is correct
65	Correct	266 ms	33272 KB	Output is correct
66	Correct	267 ms	33272 KB	Output is correct
67	Correct	251 ms	33272 KB	Output is correct
68	Correct	257 ms	33400 KB	Output is correct
69	Correct	235 ms	33272 KB	Output is correct
70	Correct	5 ms	384 KB	Output is correct

답안 #224860

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