oj.uz

Submission #853405

# Submission time Handle Problem Language Result Execution time Memory
853405 2023-09-24T09:39:32 Z annabeth9680 Pilot (NOI19_pilot) C++17
40 / 100
 30 ms 5572 KB 
#include <bits/stdc++.h>
using namespace std;
int res = 0;
struct dsu{
    vector<int> D,dep;
    void init(int N){
        D.resize(N+1);
        dep.resize(N+1);
        for(int i = 0; i<=N;++i){
            D[i] = i; dep[i] = 1;
        }
    }
    int finden(int x){
        return D[x] = (D[x] == x ? x : finden(D[x]));
    }
    void unite(int a, int b){
        a = finden(a); b = finden(b);
        if(a == b) return;
        res += dep[a]*dep[b];
        D[a] = b; dep[b] += dep[a];
    }
}DSU;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,Q; cin >> N >> Q;
    vector<int> height(N),ans(Q);
    for(int i = 0;i<N;++i) cin >> height[i];
    DSU.init(N);
    vector<pair<int,int>> queries, edges;
    for(int i = 0;i<Q;++i){
        int x; cin >> x;
        queries.push_back({x,i});
    }
    for(int i = 0;i<N;++i) edges.push_back({height[i],i});
    sort(queries.begin(),queries.end()); sort(edges.begin(),edges.end());
    int pos = 0;
    for(int i = 0;i<Q;++i){
        while(pos < N && queries[i].first >= edges[pos].first){
            DSU.unite(edges[pos].second,edges[pos].second+1);
            pos++;
        }
        ans[queries[i].second] = res;
    }
    for(int i = 0;i<Q;++i) cout << ans[i] << " ";
    cout << "\n";
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 356 KB Output is correct
14 Correct 1 ms 452 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 356 KB Output is correct
14 Correct 1 ms 452 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 452 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 356 KB Output is correct
14 Correct 1 ms 452 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 452 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 516 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Incorrect 16 ms 3132 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 356 KB Output is correct
14 Correct 1 ms 452 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 452 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 516 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Incorrect 16 ms 3132 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 356 KB Output is correct
14 Correct 1 ms 452 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 452 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 516 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Incorrect 16 ms 3132 KB Output isn't correct
27 Halted 0 ms 0 KB -