oj.uz

Submission #552564

# Submission time Handle Problem Language Result Execution time Memory
552564 2022-04-23T10:08:17 Z RaresFelix Pilot (NOI19_pilot) C++17
40 / 100
 49 ms 11604 KB 
#include <bits/stdc++.h>
#define MN 1000071
#pragma GCC optimize("O3")
using namespace std;
int n, q, A[MN], On[MN];
using ll = long long;
ll rez;
vector<pair<int, int> > Ord;

int P[MN], S[MN];

void init() {
    for(int i = 0; i < MN; ++i)
        S[i] = 1, P[i] = i;
}

int repr(int u) {
    return P[u] == u ? u : (P[u] = repr(P[u]));
}

void uni(int u, int v) {
    u = repr(u), v = repr(v);
    if(u == v) return;
    if(S[u] < S[v]) swap(u, v);
    rez -= 1ll * S[v] * (S[v] + 1) / 2;
    rez -= 1ll * S[u] * (S[u] + 1) / 2;
    S[u] += S[v];
    rez += 1ll * S[u] * (S[u] + 1) / 2;
    P[v] = u;
}

void activ(int p) {
    On[p] = 1, ++rez;
    if(On[p + 1]) uni(p, p + 1);
    if(On[p - 1]) uni(p, p - 1);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    init();
    for(int i = 1; i <= n; ++i) {
        cin >> A[i];
        Ord.push_back({A[i], i});
    }
    sort(Ord.begin(), Ord.end());
    vector<pair<int, int> > Q;
    for(int i = 1, a; i <= q; ++i) {
        cin >> a;
        Q.push_back({a, i-1});
    }
    sort(Q.begin(), Q.end());
    vector<int> R(q);
    auto it = Q.begin();
    for(auto [a, b] : Ord) {
        while(it != Q.end() && it->first < a)
            R[it->second] = rez, ++it;
        activ(b);
    }
    while(it != Q.end()) R[it->second] = rez, ++it;
    for(auto it : R) cout << it << "\n";
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 3 ms 8148 KB Output is correct
8 Correct 4 ms 8076 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 3 ms 8148 KB Output is correct
8 Correct 4 ms 8076 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 5 ms 8148 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 3 ms 8148 KB Output is correct
8 Correct 4 ms 8076 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 5 ms 8148 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 3 ms 8148 KB Output is correct
18 Correct 3 ms 8148 KB Output is correct
19 Correct 4 ms 8148 KB Output is correct
20 Correct 5 ms 8148 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 3 ms 8148 KB Output is correct
8 Correct 4 ms 8076 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 5 ms 8148 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 3 ms 8148 KB Output is correct
18 Correct 3 ms 8148 KB Output is correct
19 Correct 4 ms 8148 KB Output is correct
20 Correct 5 ms 8148 KB Output is correct
21 Correct 4 ms 8148 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 4 ms 8148 KB Output is correct
24 Correct 6 ms 8148 KB Output is correct
25 Correct 4 ms 8148 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 9700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 11596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 3 ms 8148 KB Output is correct
8 Correct 4 ms 8076 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Incorrect 25 ms 9700 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 3 ms 8148 KB Output is correct
8 Correct 4 ms 8076 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 5 ms 8148 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 3 ms 8148 KB Output is correct
18 Correct 3 ms 8148 KB Output is correct
19 Correct 4 ms 8148 KB Output is correct
20 Correct 5 ms 8148 KB Output is correct
21 Correct 4 ms 8148 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 4 ms 8148 KB Output is correct
24 Correct 6 ms 8148 KB Output is correct
25 Correct 4 ms 8148 KB Output is correct
26 Incorrect 25 ms 9700 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 3 ms 8148 KB Output is correct
8 Correct 4 ms 8076 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 5 ms 8148 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 3 ms 8148 KB Output is correct
18 Correct 3 ms 8148 KB Output is correct
19 Correct 4 ms 8148 KB Output is correct
20 Correct 5 ms 8148 KB Output is correct
21 Correct 4 ms 8148 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 4 ms 8148 KB Output is correct
24 Correct 6 ms 8148 KB Output is correct
25 Correct 4 ms 8148 KB Output is correct
26 Incorrect 25 ms 9700 KB Output isn't correct
27 Halted 0 ms 0 KB -