답안 #1027581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1027581	2024-07-19T07:45:43 Z	kkkkkkkk	Mountains (NOI20_mountains)	C++14	100 / 100	562 ms	55380 KB

Mountains

#include <bits/stdc++.h>

using namespace std;

#define int long long

int tree[1200005], a[300005];

void update(int k, int left, int right, int poz) {
    if (left>right||right<poz||left>poz)
        return;
    if (left==right) {
        if (left==poz)
            tree[k]++;
        return;
    }
    int mid=(left+right)/2;
    update(2*k, left, mid, poz);
    update(2*k+1, mid+1, right, poz);
    tree[k]=tree[2*k]+tree[2*k+1];
}

int query(int k, int left, int right, int l, int r) {
    if (right<left||right<l||left>r)
        return 0;
    if (l<=left&&right<=r)
        return tree[k];
    int mid=(left+right)/2;
    int r1=query(2*k, left, mid, l, r);
    int r2=query(2*k+1, mid+1, right, l, r);
    return r1+r2;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    set<int> s;
    for (int i=0;i<n;i++) {
        cin >> a[i];
        s.insert(a[i]);
    }
    map<int,int> compressed;
    int br=0;
    for (auto x:s)
        compressed[x]=br, br++;
    for (int i=0;i<n;i++)
        a[i]=compressed[a[i]];
    update(1, 0, n-1, a[0]);
    int rez1[n]={0}, rez2[n]={0};
    for (int i=1;i<n-1;i++) {
        rez1[i]=query(1, 0, n-1, 0, a[i]-1);
        update(1, 0, n-1, a[i]);
    }
    memset(tree, 0, sizeof(tree));
    update(1, 0, n-1, a[n-1]);
    for (int i=n-2;i>0;i--) {
        rez2[i]=query(1, 0, n-1, 0, a[i]-1);
        update(1, 0, n-1, a[i]);
    }
    int rez=0;
    for (int i=1;i<n-1;i++)
        rez+=rez1[i]*rez2[i];
    cout << rez;

    return 0;
}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9820 KB	Output is correct
2	Correct	311 ms	55112 KB	Output is correct
3	Correct	344 ms	55108 KB	Output is correct
4	Correct	308 ms	55272 KB	Output is correct
5	Correct	355 ms	55080 KB	Output is correct
6	Correct	305 ms	55184 KB	Output is correct
7	Correct	297 ms	55188 KB	Output is correct
8	Correct	321 ms	55128 KB	Output is correct
9	Correct	274 ms	39252 KB	Output is correct
10	Correct	238 ms	39304 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	105 ms	17236 KB	Output is correct
2	Correct	110 ms	17236 KB	Output is correct
3	Correct	113 ms	17236 KB	Output is correct
4	Correct	112 ms	17240 KB	Output is correct
5	Correct	115 ms	17344 KB	Output is correct
6	Correct	108 ms	17444 KB	Output is correct
7	Correct	108 ms	17236 KB	Output is correct
8	Correct	101 ms	17436 KB	Output is correct
9	Correct	95 ms	17448 KB	Output is correct
10	Correct	3 ms	9820 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	105 ms	17236 KB	Output is correct
2	Correct	110 ms	17236 KB	Output is correct
3	Correct	113 ms	17236 KB	Output is correct
4	Correct	112 ms	17240 KB	Output is correct
5	Correct	115 ms	17344 KB	Output is correct
6	Correct	108 ms	17444 KB	Output is correct
7	Correct	108 ms	17236 KB	Output is correct
8	Correct	101 ms	17436 KB	Output is correct
9	Correct	95 ms	17448 KB	Output is correct
10	Correct	3 ms	9820 KB	Output is correct
11	Correct	146 ms	17712 KB	Output is correct
12	Correct	148 ms	17492 KB	Output is correct
13	Correct	147 ms	17492 KB	Output is correct
14	Correct	144 ms	17708 KB	Output is correct
15	Correct	149 ms	17620 KB	Output is correct
16	Correct	141 ms	17492 KB	Output is correct
17	Correct	138 ms	17492 KB	Output is correct
18	Correct	166 ms	17704 KB	Output is correct
19	Correct	120 ms	17708 KB	Output is correct
20	Correct	2 ms	9820 KB	Output is correct

Subtask #4
36.0 / 36.0

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

Subtask #5
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9820 KB	Output is correct
2	Correct	2 ms	9820 KB	Output is correct
3	Correct	2 ms	10052 KB	Output is correct
4	Correct	2 ms	9820 KB	Output is correct
5	Correct	2 ms	9820 KB	Output is correct
6	Correct	2 ms	9820 KB	Output is correct
7	Correct	2 ms	9856 KB	Output is correct
8	Correct	2 ms	9820 KB	Output is correct
9	Correct	3 ms	9820 KB	Output is correct
10	Correct	2 ms	9820 KB	Output is correct
11	Correct	12 ms	11356 KB	Output is correct
12	Correct	12 ms	11428 KB	Output is correct
13	Correct	12 ms	11356 KB	Output is correct
14	Correct	12 ms	11460 KB	Output is correct
15	Correct	11 ms	11356 KB	Output is correct
16	Correct	11 ms	11356 KB	Output is correct
17	Correct	12 ms	11476 KB	Output is correct
18	Correct	10 ms	10844 KB	Output is correct
19	Correct	7 ms	10300 KB	Output is correct
20	Correct	1 ms	9936 KB	Output is correct

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	105 ms	17236 KB	Output is correct
2	Correct	110 ms	17236 KB	Output is correct
3	Correct	113 ms	17236 KB	Output is correct
4	Correct	112 ms	17240 KB	Output is correct
5	Correct	115 ms	17344 KB	Output is correct
6	Correct	108 ms	17444 KB	Output is correct
7	Correct	108 ms	17236 KB	Output is correct
8	Correct	101 ms	17436 KB	Output is correct
9	Correct	95 ms	17448 KB	Output is correct
10	Correct	3 ms	9820 KB	Output is correct
11	Correct	146 ms	17712 KB	Output is correct
12	Correct	148 ms	17492 KB	Output is correct
13	Correct	147 ms	17492 KB	Output is correct
14	Correct	144 ms	17708 KB	Output is correct
15	Correct	149 ms	17620 KB	Output is correct
16	Correct	141 ms	17492 KB	Output is correct
17	Correct	138 ms	17492 KB	Output is correct
18	Correct	166 ms	17704 KB	Output is correct
19	Correct	120 ms	17708 KB	Output is correct
20	Correct	2 ms	9820 KB	Output is correct
21	Correct	366 ms	28868 KB	Output is correct
22	Correct	403 ms	29012 KB	Output is correct
23	Correct	326 ms	29016 KB	Output is correct
24	Correct	346 ms	28756 KB	Output is correct
25	Correct	353 ms	29012 KB	Output is correct
26	Correct	349 ms	29012 KB	Output is correct
27	Correct	352 ms	29156 KB	Output is correct
28	Correct	240 ms	28756 KB	Output is correct
29	Correct	205 ms	28756 KB	Output is correct
30	Correct	2 ms	9820 KB	Output is correct

Subtask #7
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9820 KB	Output is correct
2	Correct	311 ms	55112 KB	Output is correct
3	Correct	344 ms	55108 KB	Output is correct
4	Correct	308 ms	55272 KB	Output is correct
5	Correct	355 ms	55080 KB	Output is correct
6	Correct	305 ms	55184 KB	Output is correct
7	Correct	297 ms	55188 KB	Output is correct
8	Correct	321 ms	55128 KB	Output is correct
9	Correct	274 ms	39252 KB	Output is correct
10	Correct	238 ms	39304 KB	Output is correct
11	Correct	105 ms	17236 KB	Output is correct
12	Correct	110 ms	17236 KB	Output is correct
13	Correct	113 ms	17236 KB	Output is correct
14	Correct	112 ms	17240 KB	Output is correct
15	Correct	115 ms	17344 KB	Output is correct
16	Correct	108 ms	17444 KB	Output is correct
17	Correct	108 ms	17236 KB	Output is correct
18	Correct	101 ms	17436 KB	Output is correct
19	Correct	95 ms	17448 KB	Output is correct
20	Correct	3 ms	9820 KB	Output is correct
21	Correct	146 ms	17712 KB	Output is correct
22	Correct	148 ms	17492 KB	Output is correct
23	Correct	147 ms	17492 KB	Output is correct
24	Correct	144 ms	17708 KB	Output is correct
25	Correct	149 ms	17620 KB	Output is correct
26	Correct	141 ms	17492 KB	Output is correct
27	Correct	138 ms	17492 KB	Output is correct
28	Correct	166 ms	17704 KB	Output is correct
29	Correct	120 ms	17708 KB	Output is correct
30	Correct	2 ms	9820 KB	Output is correct
31	Correct	2 ms	9820 KB	Output is correct
32	Correct	2 ms	9820 KB	Output is correct
33	Correct	2 ms	10052 KB	Output is correct
34	Correct	2 ms	9820 KB	Output is correct
35	Correct	2 ms	9820 KB	Output is correct
36	Correct	2 ms	9820 KB	Output is correct
37	Correct	2 ms	9856 KB	Output is correct
38	Correct	2 ms	9820 KB	Output is correct
39	Correct	3 ms	9820 KB	Output is correct
40	Correct	2 ms	9820 KB	Output is correct
41	Correct	12 ms	11356 KB	Output is correct
42	Correct	12 ms	11428 KB	Output is correct
43	Correct	12 ms	11356 KB	Output is correct
44	Correct	12 ms	11460 KB	Output is correct
45	Correct	11 ms	11356 KB	Output is correct
46	Correct	11 ms	11356 KB	Output is correct
47	Correct	12 ms	11476 KB	Output is correct
48	Correct	10 ms	10844 KB	Output is correct
49	Correct	7 ms	10300 KB	Output is correct
50	Correct	1 ms	9936 KB	Output is correct
51	Correct	366 ms	28868 KB	Output is correct
52	Correct	403 ms	29012 KB	Output is correct
53	Correct	326 ms	29016 KB	Output is correct
54	Correct	346 ms	28756 KB	Output is correct
55	Correct	353 ms	29012 KB	Output is correct
56	Correct	349 ms	29012 KB	Output is correct
57	Correct	352 ms	29156 KB	Output is correct
58	Correct	240 ms	28756 KB	Output is correct
59	Correct	205 ms	28756 KB	Output is correct
60	Correct	2 ms	9820 KB	Output is correct
61	Correct	536 ms	55176 KB	Output is correct
62	Correct	562 ms	55124 KB	Output is correct
63	Correct	516 ms	55244 KB	Output is correct
64	Correct	515 ms	55124 KB	Output is correct
65	Correct	479 ms	55124 KB	Output is correct
66	Correct	484 ms	55380 KB	Output is correct
67	Correct	491 ms	55088 KB	Output is correct
68	Correct	423 ms	39372 KB	Output is correct
69	Correct	396 ms	32912 KB	Output is correct
70	Correct	2 ms	9820 KB	Output is correct

답안 #1027581

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