답안 #227172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
227172	2020-04-26T09:58:54 Z	TheKingAleks	Mountains (NOI20_mountains)	C++14	100 / 100	981 ms	58892 KB

Mountains

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const ll MAX_N = 3e5+2;
ll a[MAX_N];
ll res;
set<ll> s;
unordered_map<ll,ll> m;
ll br=1;
vector<ll> tree1(MAX_N*4);
vector<ll> tree2(MAX_N*4);
void update(vector<ll> &tree,ll node,ll tl,ll tr,ll l,ll r)
{
    if(tl > r || tr < l)return;
    if(tl == tr)
    {
        tree[node]++;
        return;
    }
    ll mid = (tl+tr)/2;
    update(tree,node*2,tl,mid,l,r);
    update(tree,node*2+1,mid+1,tr,l,r);
    tree[node] = tree[node*2]+tree[node*2+1];
}
ll query(vector<ll> &tree,ll node,ll tl,ll tr,ll l,ll r)
{
    if(tl > r || tr < l)return 0;
    if(tl >= l && tr <= r)
    {
        return tree[node];
    }
    ll mid = (tl+tr)/2;
    return query(tree,node*2,tl,mid,l,r)+query(tree,node*2+1,mid+1,tr,l,r);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    vector<ll> l(n+2);
    vector<ll> r(n+2);
    for(ll i=0; i<n; i++)
    {
        cin>>a[i];
        s.insert(a[i]);
    }
    for(auto &it : s)
    {
        m[it] = br;
        br++;
    }
    br--;
    update(tree1,1,1,br,m[a[0]],m[a[0]]);
    for(ll i=1; i<n; i++)
    {
        l[i] = query(tree1,1,1,br,1,m[a[i]]-1);
        update(tree1,1,1,br,m[a[i]],m[a[i]]);
    }
    update(tree2,1,1,br,m[a[n-1]],m[a[n-1]]);
    for(ll i=n-2; i>=0; i--)
    {
        r[i] = query(tree2,1,1,br,1,m[a[i]]-1);
        update(tree2,1,1,br,m[a[i]],m[a[i]]);
    }
    for(ll i=0;i<n;i++)
    {
        res+=(l[i]*r[i]);
    }
    cout<<res<<endl;

}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	19072 KB	Output is correct
2	Correct	568 ms	53256 KB	Output is correct
3	Correct	573 ms	58612 KB	Output is correct
4	Correct	576 ms	58636 KB	Output is correct
5	Correct	571 ms	58760 KB	Output is correct
6	Correct	588 ms	58740 KB	Output is correct
7	Correct	584 ms	58636 KB	Output is correct
8	Correct	612 ms	58768 KB	Output is correct
9	Correct	372 ms	45756 KB	Output is correct
10	Correct	363 ms	45632 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	26108 KB	Output is correct
2	Correct	59 ms	26104 KB	Output is correct
3	Correct	57 ms	26104 KB	Output is correct
4	Correct	57 ms	26104 KB	Output is correct
5	Correct	58 ms	26232 KB	Output is correct
6	Correct	56 ms	26104 KB	Output is correct
7	Correct	56 ms	26240 KB	Output is correct
8	Correct	53 ms	26104 KB	Output is correct
9	Correct	53 ms	26232 KB	Output is correct
10	Correct	13 ms	19072 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	26108 KB	Output is correct
2	Correct	59 ms	26104 KB	Output is correct
3	Correct	57 ms	26104 KB	Output is correct
4	Correct	57 ms	26104 KB	Output is correct
5	Correct	58 ms	26232 KB	Output is correct
6	Correct	56 ms	26104 KB	Output is correct
7	Correct	56 ms	26240 KB	Output is correct
8	Correct	53 ms	26104 KB	Output is correct
9	Correct	53 ms	26232 KB	Output is correct
10	Correct	13 ms	19072 KB	Output is correct
11	Correct	154 ms	26232 KB	Output is correct
12	Correct	157 ms	26360 KB	Output is correct
13	Correct	155 ms	26172 KB	Output is correct
14	Correct	153 ms	26240 KB	Output is correct
15	Correct	154 ms	26360 KB	Output is correct
16	Correct	157 ms	26232 KB	Output is correct
17	Correct	155 ms	26232 KB	Output is correct
18	Correct	113 ms	26232 KB	Output is correct
19	Correct	102 ms	26232 KB	Output is correct
20	Correct	13 ms	19072 KB	Output is correct

Subtask #4
36.0 / 36.0

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

Subtask #5
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	19200 KB	Output is correct
2	Correct	14 ms	19200 KB	Output is correct
3	Correct	14 ms	19200 KB	Output is correct
4	Correct	13 ms	19200 KB	Output is correct
5	Correct	14 ms	19200 KB	Output is correct
6	Correct	14 ms	19200 KB	Output is correct
7	Correct	14 ms	19200 KB	Output is correct
8	Correct	13 ms	19200 KB	Output is correct
9	Correct	13 ms	19200 KB	Output is correct
10	Correct	13 ms	19072 KB	Output is correct
11	Correct	29 ms	20352 KB	Output is correct
12	Correct	29 ms	20224 KB	Output is correct
13	Correct	28 ms	20224 KB	Output is correct
14	Correct	29 ms	20224 KB	Output is correct
15	Correct	29 ms	20224 KB	Output is correct
16	Correct	30 ms	20352 KB	Output is correct
17	Correct	29 ms	20224 KB	Output is correct
18	Correct	24 ms	19712 KB	Output is correct
19	Correct	19 ms	19456 KB	Output is correct
20	Correct	13 ms	19200 KB	Output is correct

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	26108 KB	Output is correct
2	Correct	59 ms	26104 KB	Output is correct
3	Correct	57 ms	26104 KB	Output is correct
4	Correct	57 ms	26104 KB	Output is correct
5	Correct	58 ms	26232 KB	Output is correct
6	Correct	56 ms	26104 KB	Output is correct
7	Correct	56 ms	26240 KB	Output is correct
8	Correct	53 ms	26104 KB	Output is correct
9	Correct	53 ms	26232 KB	Output is correct
10	Correct	13 ms	19072 KB	Output is correct
11	Correct	154 ms	26232 KB	Output is correct
12	Correct	157 ms	26360 KB	Output is correct
13	Correct	155 ms	26172 KB	Output is correct
14	Correct	153 ms	26240 KB	Output is correct
15	Correct	154 ms	26360 KB	Output is correct
16	Correct	157 ms	26232 KB	Output is correct
17	Correct	155 ms	26232 KB	Output is correct
18	Correct	113 ms	26232 KB	Output is correct
19	Correct	102 ms	26232 KB	Output is correct
20	Correct	13 ms	19072 KB	Output is correct
21	Correct	491 ms	34588 KB	Output is correct
22	Correct	478 ms	34576 KB	Output is correct
23	Correct	463 ms	34568 KB	Output is correct
24	Correct	480 ms	34440 KB	Output is correct
25	Correct	486 ms	34624 KB	Output is correct
26	Correct	475 ms	34568 KB	Output is correct
27	Correct	479 ms	34568 KB	Output is correct
28	Correct	277 ms	34440 KB	Output is correct
29	Correct	281 ms	34568 KB	Output is correct
30	Correct	14 ms	19200 KB	Output is correct

Subtask #7
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	19072 KB	Output is correct
2	Correct	568 ms	53256 KB	Output is correct
3	Correct	573 ms	58612 KB	Output is correct
4	Correct	576 ms	58636 KB	Output is correct
5	Correct	571 ms	58760 KB	Output is correct
6	Correct	588 ms	58740 KB	Output is correct
7	Correct	584 ms	58636 KB	Output is correct
8	Correct	612 ms	58768 KB	Output is correct
9	Correct	372 ms	45756 KB	Output is correct
10	Correct	363 ms	45632 KB	Output is correct
11	Correct	56 ms	26108 KB	Output is correct
12	Correct	59 ms	26104 KB	Output is correct
13	Correct	57 ms	26104 KB	Output is correct
14	Correct	57 ms	26104 KB	Output is correct
15	Correct	58 ms	26232 KB	Output is correct
16	Correct	56 ms	26104 KB	Output is correct
17	Correct	56 ms	26240 KB	Output is correct
18	Correct	53 ms	26104 KB	Output is correct
19	Correct	53 ms	26232 KB	Output is correct
20	Correct	13 ms	19072 KB	Output is correct
21	Correct	154 ms	26232 KB	Output is correct
22	Correct	157 ms	26360 KB	Output is correct
23	Correct	155 ms	26172 KB	Output is correct
24	Correct	153 ms	26240 KB	Output is correct
25	Correct	154 ms	26360 KB	Output is correct
26	Correct	157 ms	26232 KB	Output is correct
27	Correct	155 ms	26232 KB	Output is correct
28	Correct	113 ms	26232 KB	Output is correct
29	Correct	102 ms	26232 KB	Output is correct
30	Correct	13 ms	19072 KB	Output is correct
31	Correct	13 ms	19200 KB	Output is correct
32	Correct	14 ms	19200 KB	Output is correct
33	Correct	14 ms	19200 KB	Output is correct
34	Correct	13 ms	19200 KB	Output is correct
35	Correct	14 ms	19200 KB	Output is correct
36	Correct	14 ms	19200 KB	Output is correct
37	Correct	14 ms	19200 KB	Output is correct
38	Correct	13 ms	19200 KB	Output is correct
39	Correct	13 ms	19200 KB	Output is correct
40	Correct	13 ms	19072 KB	Output is correct
41	Correct	29 ms	20352 KB	Output is correct
42	Correct	29 ms	20224 KB	Output is correct
43	Correct	28 ms	20224 KB	Output is correct
44	Correct	29 ms	20224 KB	Output is correct
45	Correct	29 ms	20224 KB	Output is correct
46	Correct	30 ms	20352 KB	Output is correct
47	Correct	29 ms	20224 KB	Output is correct
48	Correct	24 ms	19712 KB	Output is correct
49	Correct	19 ms	19456 KB	Output is correct
50	Correct	13 ms	19200 KB	Output is correct
51	Correct	491 ms	34588 KB	Output is correct
52	Correct	478 ms	34576 KB	Output is correct
53	Correct	463 ms	34568 KB	Output is correct
54	Correct	480 ms	34440 KB	Output is correct
55	Correct	486 ms	34624 KB	Output is correct
56	Correct	475 ms	34568 KB	Output is correct
57	Correct	479 ms	34568 KB	Output is correct
58	Correct	277 ms	34440 KB	Output is correct
59	Correct	281 ms	34568 KB	Output is correct
60	Correct	14 ms	19200 KB	Output is correct
61	Correct	977 ms	58812 KB	Output is correct
62	Correct	973 ms	58688 KB	Output is correct
63	Correct	976 ms	58764 KB	Output is correct
64	Correct	978 ms	58760 KB	Output is correct
65	Correct	981 ms	58764 KB	Output is correct
66	Correct	978 ms	58892 KB	Output is correct
67	Correct	974 ms	58764 KB	Output is correct
68	Correct	679 ms	45756 KB	Output is correct
69	Correct	540 ms	40072 KB	Output is correct
70	Correct	13 ms	19200 KB	Output is correct

답안 #227172

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