답안 #888926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888926	2023-12-18T11:59:20 Z	vjudge1	Mountains (NOI20_mountains)	C++17	100 / 100	84 ms	17840 KB

Mountains

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

struct FenwickTree {
    int n;
    vector<int> data;

    FenwickTree(int n) : n(n), data(n + 1) {}

    void update(int idx, int val) {
        for (; idx <= n; idx += idx & -idx)
            data[idx] += val;
    }

    int get(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx)
            res += data[idx];
        return res;
    }
};

int n;
i64 res, a[mxN];
vector<pair<i64, int>> v;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        v.emplace_back(a[i], i);
    }
    sort(all(v));

    FenwickTree fenw(n);
    for (int i = 0; i < n;) {
        int ptr = i;
        while (ptr < n && v[ptr].ff == v[i].ff) {
            int lt = fenw.get(v[ptr].ss), rt = i - lt;
            res += 1ll * lt * rt;
            ++ptr;
        }
        for (int j = i; j < ptr; ++j)
            fenw.update(v[j].ss, 1);
        i = ptr;
    }
    cout << res << endl;
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	47 ms	17012 KB	Output is correct
3	Correct	47 ms	16680 KB	Output is correct
4	Correct	48 ms	17700 KB	Output is correct
5	Correct	53 ms	16580 KB	Output is correct
6	Correct	47 ms	16080 KB	Output is correct
7	Correct	48 ms	16816 KB	Output is correct
8	Correct	48 ms	17840 KB	Output is correct
9	Correct	52 ms	16576 KB	Output is correct
10	Correct	52 ms	16480 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	12484 KB	Output is correct
2	Correct	48 ms	11724 KB	Output is correct
3	Correct	46 ms	13516 KB	Output is correct
4	Correct	43 ms	13008 KB	Output is correct
5	Correct	46 ms	12496 KB	Output is correct
6	Correct	43 ms	11984 KB	Output is correct
7	Correct	43 ms	11768 KB	Output is correct
8	Correct	26 ms	12240 KB	Output is correct
9	Correct	31 ms	12668 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	12484 KB	Output is correct
2	Correct	48 ms	11724 KB	Output is correct
3	Correct	46 ms	13516 KB	Output is correct
4	Correct	43 ms	13008 KB	Output is correct
5	Correct	46 ms	12496 KB	Output is correct
6	Correct	43 ms	11984 KB	Output is correct
7	Correct	43 ms	11768 KB	Output is correct
8	Correct	26 ms	12240 KB	Output is correct
9	Correct	31 ms	12668 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	52 ms	11728 KB	Output is correct
12	Correct	51 ms	12484 KB	Output is correct
13	Correct	52 ms	11984 KB	Output is correct
14	Correct	52 ms	13264 KB	Output is correct
15	Correct	52 ms	13260 KB	Output is correct
16	Correct	52 ms	12496 KB	Output is correct
17	Correct	52 ms	11848 KB	Output is correct
18	Correct	30 ms	12024 KB	Output is correct
19	Correct	29 ms	12236 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct

Subtask #4
36.0 / 36.0

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

Subtask #5
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	472 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	3 ms	992 KB	Output is correct
12	Correct	3 ms	1116 KB	Output is correct
13	Correct	2 ms	992 KB	Output is correct
14	Correct	3 ms	992 KB	Output is correct
15	Correct	3 ms	992 KB	Output is correct
16	Correct	2 ms	992 KB	Output is correct
17	Correct	3 ms	992 KB	Output is correct
18	Correct	3 ms	1116 KB	Output is correct
19	Correct	2 ms	860 KB	Output is correct
20	Correct	0 ms	344 KB	Output is correct

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	12484 KB	Output is correct
2	Correct	48 ms	11724 KB	Output is correct
3	Correct	46 ms	13516 KB	Output is correct
4	Correct	43 ms	13008 KB	Output is correct
5	Correct	46 ms	12496 KB	Output is correct
6	Correct	43 ms	11984 KB	Output is correct
7	Correct	43 ms	11768 KB	Output is correct
8	Correct	26 ms	12240 KB	Output is correct
9	Correct	31 ms	12668 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	52 ms	11728 KB	Output is correct
12	Correct	51 ms	12484 KB	Output is correct
13	Correct	52 ms	11984 KB	Output is correct
14	Correct	52 ms	13264 KB	Output is correct
15	Correct	52 ms	13260 KB	Output is correct
16	Correct	52 ms	12496 KB	Output is correct
17	Correct	52 ms	11848 KB	Output is correct
18	Correct	30 ms	12024 KB	Output is correct
19	Correct	29 ms	12236 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	57 ms	13776 KB	Output is correct
22	Correct	57 ms	13872 KB	Output is correct
23	Correct	56 ms	12740 KB	Output is correct
24	Correct	57 ms	14020 KB	Output is correct
25	Correct	57 ms	13008 KB	Output is correct
26	Correct	58 ms	13008 KB	Output is correct
27	Correct	62 ms	14544 KB	Output is correct
28	Correct	35 ms	14032 KB	Output is correct
29	Correct	34 ms	12740 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct

Subtask #7
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	47 ms	17012 KB	Output is correct
3	Correct	47 ms	16680 KB	Output is correct
4	Correct	48 ms	17700 KB	Output is correct
5	Correct	53 ms	16580 KB	Output is correct
6	Correct	47 ms	16080 KB	Output is correct
7	Correct	48 ms	16816 KB	Output is correct
8	Correct	48 ms	17840 KB	Output is correct
9	Correct	52 ms	16576 KB	Output is correct
10	Correct	52 ms	16480 KB	Output is correct
11	Correct	42 ms	12484 KB	Output is correct
12	Correct	48 ms	11724 KB	Output is correct
13	Correct	46 ms	13516 KB	Output is correct
14	Correct	43 ms	13008 KB	Output is correct
15	Correct	46 ms	12496 KB	Output is correct
16	Correct	43 ms	11984 KB	Output is correct
17	Correct	43 ms	11768 KB	Output is correct
18	Correct	26 ms	12240 KB	Output is correct
19	Correct	31 ms	12668 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	52 ms	11728 KB	Output is correct
22	Correct	51 ms	12484 KB	Output is correct
23	Correct	52 ms	11984 KB	Output is correct
24	Correct	52 ms	13264 KB	Output is correct
25	Correct	52 ms	13260 KB	Output is correct
26	Correct	52 ms	12496 KB	Output is correct
27	Correct	52 ms	11848 KB	Output is correct
28	Correct	30 ms	12024 KB	Output is correct
29	Correct	29 ms	12236 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	472 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	1 ms	348 KB	Output is correct
39	Correct	0 ms	348 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	3 ms	992 KB	Output is correct
42	Correct	3 ms	1116 KB	Output is correct
43	Correct	2 ms	992 KB	Output is correct
44	Correct	3 ms	992 KB	Output is correct
45	Correct	3 ms	992 KB	Output is correct
46	Correct	2 ms	992 KB	Output is correct
47	Correct	3 ms	992 KB	Output is correct
48	Correct	3 ms	1116 KB	Output is correct
49	Correct	2 ms	860 KB	Output is correct
50	Correct	0 ms	344 KB	Output is correct
51	Correct	57 ms	13776 KB	Output is correct
52	Correct	57 ms	13872 KB	Output is correct
53	Correct	56 ms	12740 KB	Output is correct
54	Correct	57 ms	14020 KB	Output is correct
55	Correct	57 ms	13008 KB	Output is correct
56	Correct	58 ms	13008 KB	Output is correct
57	Correct	62 ms	14544 KB	Output is correct
58	Correct	35 ms	14032 KB	Output is correct
59	Correct	34 ms	12740 KB	Output is correct
60	Correct	1 ms	348 KB	Output is correct
61	Correct	73 ms	16576 KB	Output is correct
62	Correct	71 ms	16072 KB	Output is correct
63	Correct	70 ms	17600 KB	Output is correct
64	Correct	70 ms	16832 KB	Output is correct
65	Correct	75 ms	17008 KB	Output is correct
66	Correct	84 ms	17072 KB	Output is correct
67	Correct	70 ms	17524 KB	Output is correct
68	Correct	75 ms	16376 KB	Output is correct
69	Correct	58 ms	13528 KB	Output is correct
70	Correct	1 ms	348 KB	Output is correct

답안 #888926

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