oj.uz

답안 #1062383

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1062383 2024-08-17T05:27:56 Z CodeLakVN Pilot (NOI19_pilot) C++17
100 / 100
 336 ms 83028 KB 
#include <bits/stdc++.h>

#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define task "PILOT"
#define ll long long
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maximize(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool minimize(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)1e6 + 9;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int n, numQuery;
int a[N], query[N];

namespace sub3 {
    bool valid() {
        return max(n, numQuery) <= 200;
    }

    void solve() {
        FOR(i, 1, numQuery) {
            int ans = 0;
            FOR(s, 1, n) {
                if (a[s] > query[i]) continue;
                FOR(e, s, n) {
                    if (a[e] <= query[i]) ans++;
                    else break;
                }
            }
            cout << ans << "\n";
        }
    }
}

namespace sub4 {
    bool valid() {
        return 1LL * n * numQuery <= (ll)1e8;
    }

    void solve() {
        FOR(i, 1, numQuery) {
            int ans = 0;
            FOR(s, 1, n) {
                if (a[s] > query[i]) continue;
                int e = s;
                while (e <=n && a[e] <= query[i]) e++;
                e--;
                int cnt = (e - s + 1);
                ans += cnt * (cnt + 1) / 2;
                s = e;
            }
            cout << ans << "\n";
        }
    }
}

namespace subFull {
    vector<int> pos[N];
    bool vis[N];
    ll preLen[N], sufLen[N];
    ll ans[N];

    void solve() {
        int maxVal = *max_element(query + 1, query + numQuery + 1);
        FOR(i, 1, n) pos[a[i]].push_back(i);

        memset(vis, 0, sizeof(vis));

        FOR(i, 1, maxVal) {
            ans[i] = ans[i - 1];
            for (int x : pos[i]) {
                ans[i]++;
                if (vis[x - 1]) ans[i] += preLen[x - 1], sufLen[x - 1 - preLen[x - 1] + 1]++;
                if (vis[x + 1]) ans[i] += sufLen[x + 1], preLen[x + 1 + sufLen[x + 1] - 1]++;
                if (vis[x - 1] && vis[x + 1]) {
                    ans[i] += 1LL * preLen[x - 1] * sufLen[x + 1];
                    sufLen[x - 1 - preLen[x - 1] + 1] += sufLen[x + 1];
                    preLen[x + 1 + sufLen[x + 1] - 1] += preLen[x - 1];
                }
                preLen[x] = preLen[x - 1] + 1;
                sufLen[x] = sufLen[x + 1] + 1;
                vis[x] = 1;
            }
        }

        FOR(i, 1, numQuery) {
            cout << ans[query[i]] << "\n";
        }
    }
}

void main_code() {
    cin >> n >> numQuery;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, numQuery) cin >> query[i];

    subFull::solve();
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0;
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); cout << "\n"; }
}

/* Lak lu theo dieu nhac */

Compilation message

pilot.cpp: In function 'int main()':
pilot.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pilot.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 4 ms 29020 KB Output is correct
7 Correct 6 ms 35420 KB Output is correct
8 Correct 4 ms 29016 KB Output is correct
9 Correct 6 ms 35420 KB Output is correct
10 Correct 5 ms 31320 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 4 ms 29020 KB Output is correct
7 Correct 6 ms 35420 KB Output is correct
8 Correct 4 ms 29016 KB Output is correct
9 Correct 6 ms 35420 KB Output is correct
10 Correct 5 ms 31320 KB Output is correct
11 Correct 7 ms 36956 KB Output is correct
12 Correct 7 ms 36812 KB Output is correct
13 Correct 6 ms 36304 KB Output is correct
14 Correct 7 ms 36956 KB Output is correct
15 Correct 6 ms 35420 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 4 ms 29020 KB Output is correct
7 Correct 6 ms 35420 KB Output is correct
8 Correct 4 ms 29016 KB Output is correct
9 Correct 6 ms 35420 KB Output is correct
10 Correct 5 ms 31320 KB Output is correct
11 Correct 7 ms 36956 KB Output is correct
12 Correct 7 ms 36812 KB Output is correct
13 Correct 6 ms 36304 KB Output is correct
14 Correct 7 ms 36956 KB Output is correct
15 Correct 6 ms 35420 KB Output is correct
16 Correct 7 ms 36956 KB Output is correct
17 Correct 9 ms 36956 KB Output is correct
18 Correct 7 ms 36952 KB Output is correct
19 Correct 7 ms 36952 KB Output is correct
20 Correct 6 ms 36684 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 4 ms 29020 KB Output is correct
7 Correct 6 ms 35420 KB Output is correct
8 Correct 4 ms 29016 KB Output is correct
9 Correct 6 ms 35420 KB Output is correct
10 Correct 5 ms 31320 KB Output is correct
11 Correct 7 ms 36956 KB Output is correct
12 Correct 7 ms 36812 KB Output is correct
13 Correct 6 ms 36304 KB Output is correct
14 Correct 7 ms 36956 KB Output is correct
15 Correct 6 ms 35420 KB Output is correct
16 Correct 7 ms 36956 KB Output is correct
17 Correct 9 ms 36956 KB Output is correct
18 Correct 7 ms 36952 KB Output is correct
19 Correct 7 ms 36952 KB Output is correct
20 Correct 6 ms 36684 KB Output is correct
21 Correct 7 ms 36952 KB Output is correct
22 Correct 8 ms 37052 KB Output is correct
23 Correct 8 ms 36956 KB Output is correct
24 Correct 7 ms 36956 KB Output is correct
25 Correct 7 ms 36956 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 40284 KB Output is correct
2 Correct 22 ms 41304 KB Output is correct
3 Correct 18 ms 40536 KB Output is correct
4 Correct 22 ms 40928 KB Output is correct
5 Correct 19 ms 40284 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 42332 KB Output is correct
2 Correct 27 ms 42204 KB Output is correct
3 Correct 31 ms 42068 KB Output is correct
4 Correct 29 ms 42332 KB Output is correct
5 Correct 26 ms 42064 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 42332 KB Output is correct
2 Correct 28 ms 42328 KB Output is correct
3 Correct 28 ms 42076 KB Output is correct
4 Correct 36 ms 42580 KB Output is correct
5 Correct 29 ms 42332 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 4 ms 29020 KB Output is correct
7 Correct 6 ms 35420 KB Output is correct
8 Correct 4 ms 29016 KB Output is correct
9 Correct 6 ms 35420 KB Output is correct
10 Correct 5 ms 31320 KB Output is correct
11 Correct 22 ms 40284 KB Output is correct
12 Correct 22 ms 41304 KB Output is correct
13 Correct 18 ms 40536 KB Output is correct
14 Correct 22 ms 40928 KB Output is correct
15 Correct 19 ms 40284 KB Output is correct
16 Correct 16 ms 34652 KB Output is correct
17 Correct 18 ms 37892 KB Output is correct
18 Correct 17 ms 35932 KB Output is correct
19 Correct 14 ms 32344 KB Output is correct
20 Correct 19 ms 37632 KB Output is correct
21 Correct 17 ms 34652 KB Output is correct
22 Correct 19 ms 37464 KB Output is correct
23 Correct 16 ms 34904 KB Output is correct
24 Correct 17 ms 35420 KB Output is correct
25 Correct 17 ms 34776 KB Output is correct

Subtask #9
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 4 ms 29020 KB Output is correct
7 Correct 6 ms 35420 KB Output is correct
8 Correct 4 ms 29016 KB Output is correct
9 Correct 6 ms 35420 KB Output is correct
10 Correct 5 ms 31320 KB Output is correct
11 Correct 7 ms 36956 KB Output is correct
12 Correct 7 ms 36812 KB Output is correct
13 Correct 6 ms 36304 KB Output is correct
14 Correct 7 ms 36956 KB Output is correct
15 Correct 6 ms 35420 KB Output is correct
16 Correct 7 ms 36956 KB Output is correct
17 Correct 9 ms 36956 KB Output is correct
18 Correct 7 ms 36952 KB Output is correct
19 Correct 7 ms 36952 KB Output is correct
20 Correct 6 ms 36684 KB Output is correct
21 Correct 7 ms 36952 KB Output is correct
22 Correct 8 ms 37052 KB Output is correct
23 Correct 8 ms 36956 KB Output is correct
24 Correct 7 ms 36956 KB Output is correct
25 Correct 7 ms 36956 KB Output is correct
26 Correct 22 ms 40284 KB Output is correct
27 Correct 22 ms 41304 KB Output is correct
28 Correct 18 ms 40536 KB Output is correct
29 Correct 22 ms 40928 KB Output is correct
30 Correct 19 ms 40284 KB Output is correct
31 Correct 29 ms 42332 KB Output is correct
32 Correct 27 ms 42204 KB Output is correct
33 Correct 31 ms 42068 KB Output is correct
34 Correct 29 ms 42332 KB Output is correct
35 Correct 26 ms 42064 KB Output is correct
36 Correct 29 ms 42332 KB Output is correct
37 Correct 28 ms 42328 KB Output is correct
38 Correct 28 ms 42076 KB Output is correct
39 Correct 36 ms 42580 KB Output is correct
40 Correct 29 ms 42332 KB Output is correct
41 Correct 16 ms 34652 KB Output is correct
42 Correct 18 ms 37892 KB Output is correct
43 Correct 17 ms 35932 KB Output is correct
44 Correct 14 ms 32344 KB Output is correct
45 Correct 19 ms 37632 KB Output is correct
46 Correct 17 ms 34652 KB Output is correct
47 Correct 19 ms 37464 KB Output is correct
48 Correct 16 ms 34904 KB Output is correct
49 Correct 17 ms 35420 KB Output is correct
50 Correct 17 ms 34776 KB Output is correct
51 Correct 31 ms 41044 KB Output is correct
52 Correct 36 ms 41860 KB Output is correct
53 Correct 31 ms 41044 KB Output is correct
54 Correct 33 ms 41820 KB Output is correct
55 Correct 30 ms 41308 KB Output is correct

Subtask #10
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 4 ms 29020 KB Output is correct
7 Correct 6 ms 35420 KB Output is correct
8 Correct 4 ms 29016 KB Output is correct
9 Correct 6 ms 35420 KB Output is correct
10 Correct 5 ms 31320 KB Output is correct
11 Correct 7 ms 36956 KB Output is correct
12 Correct 7 ms 36812 KB Output is correct
13 Correct 6 ms 36304 KB Output is correct
14 Correct 7 ms 36956 KB Output is correct
15 Correct 6 ms 35420 KB Output is correct
16 Correct 7 ms 36956 KB Output is correct
17 Correct 9 ms 36956 KB Output is correct
18 Correct 7 ms 36952 KB Output is correct
19 Correct 7 ms 36952 KB Output is correct
20 Correct 6 ms 36684 KB Output is correct
21 Correct 7 ms 36952 KB Output is correct
22 Correct 8 ms 37052 KB Output is correct
23 Correct 8 ms 36956 KB Output is correct
24 Correct 7 ms 36956 KB Output is correct
25 Correct 7 ms 36956 KB Output is correct
26 Correct 22 ms 40284 KB Output is correct
27 Correct 22 ms 41304 KB Output is correct
28 Correct 18 ms 40536 KB Output is correct
29 Correct 22 ms 40928 KB Output is correct
30 Correct 19 ms 40284 KB Output is correct
31 Correct 29 ms 42332 KB Output is correct
32 Correct 27 ms 42204 KB Output is correct
33 Correct 31 ms 42068 KB Output is correct
34 Correct 29 ms 42332 KB Output is correct
35 Correct 26 ms 42064 KB Output is correct
36 Correct 29 ms 42332 KB Output is correct
37 Correct 28 ms 42328 KB Output is correct
38 Correct 28 ms 42076 KB Output is correct
39 Correct 36 ms 42580 KB Output is correct
40 Correct 29 ms 42332 KB Output is correct
41 Correct 16 ms 34652 KB Output is correct
42 Correct 18 ms 37892 KB Output is correct
43 Correct 17 ms 35932 KB Output is correct
44 Correct 14 ms 32344 KB Output is correct
45 Correct 19 ms 37632 KB Output is correct
46 Correct 17 ms 34652 KB Output is correct
47 Correct 19 ms 37464 KB Output is correct
48 Correct 16 ms 34904 KB Output is correct
49 Correct 17 ms 35420 KB Output is correct
50 Correct 17 ms 34776 KB Output is correct
51 Correct 31 ms 41044 KB Output is correct
52 Correct 36 ms 41860 KB Output is correct
53 Correct 31 ms 41044 KB Output is correct
54 Correct 33 ms 41820 KB Output is correct
55 Correct 30 ms 41308 KB Output is correct
56 Correct 312 ms 81656 KB Output is correct
57 Correct 336 ms 82516 KB Output is correct
58 Correct 327 ms 80208 KB Output is correct
59 Correct 317 ms 81236 KB Output is correct
60 Correct 320 ms 83028 KB Output is correct