oj.uz

Submission #633406

# Submission time Handle Problem Language Result Execution time Memory
633406 2022-08-22T10:59:03 Z JJAnawat Pilot (NOI19_pilot) C++14
100 / 100
 771 ms 84660 KB 
#include<bits/stdc++.h>

using namespace std;

//maximum = 1e6;
const int mxN=1e6;
int n,q,x;
int p[mxN+5];
vector<int> h[mxN+5];
long long ans[mxN+5],sz[mxN+5];
bool vis[mxN+5];

int fp(int i){
    if(p[i]==i)
        return i;
    return p[i]=fp(p[i]);
}

long long cal(long long szx){
    return szx*(szx+1)/2;
}

long long un(int x,int y,long long sum){
    int u=fp(x),v=fp(y);
    sum-=cal(sz[u])+cal(sz[v]);
    if(sz[u]<sz[v])
        swap(u,v);
    p[v]=u;
    sz[u]+=sz[v];
    sum+=cal(sz[u]);
    return sum;
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    for(int i=1;i<=mxN;i++){
        p[i]=i;
        sz[i]=1;
    }

    for(int i=1;i<=n;i++){
        cin >> x;
        h[x].push_back(i);
    }

    for(int i=1;i<=mxN;i++){
        ans[i]=ans[i-1];
        for(auto j:h[i]){
            vis[j]=1;
            ans[i]++;
            if(vis[j-1])
                ans[i]=un(j,j-1,ans[i]);
            if(vis[j+1])
                ans[i]=un(j,j+1,ans[i]);
        }
    }

    while(q--){
        cin >> x;
        cout << ans[x] << '\n';
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43348 KB Output is correct
2 Correct 22 ms 43364 KB Output is correct
3 Correct 25 ms 43324 KB Output is correct
4 Correct 23 ms 43360 KB Output is correct
5 Correct 26 ms 43360 KB Output is correct
6 Correct 23 ms 43280 KB Output is correct
7 Correct 23 ms 43352 KB Output is correct
8 Correct 24 ms 43348 KB Output is correct
9 Correct 23 ms 43348 KB Output is correct
10 Correct 26 ms 43248 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43348 KB Output is correct
2 Correct 22 ms 43364 KB Output is correct
3 Correct 25 ms 43324 KB Output is correct
4 Correct 23 ms 43360 KB Output is correct
5 Correct 26 ms 43360 KB Output is correct
6 Correct 23 ms 43280 KB Output is correct
7 Correct 23 ms 43352 KB Output is correct
8 Correct 24 ms 43348 KB Output is correct
9 Correct 23 ms 43348 KB Output is correct
10 Correct 26 ms 43248 KB Output is correct
11 Correct 21 ms 43348 KB Output is correct
12 Correct 23 ms 43340 KB Output is correct
13 Correct 25 ms 43400 KB Output is correct
14 Correct 23 ms 43280 KB Output is correct
15 Correct 23 ms 43348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43348 KB Output is correct
2 Correct 22 ms 43364 KB Output is correct
3 Correct 25 ms 43324 KB Output is correct
4 Correct 23 ms 43360 KB Output is correct
5 Correct 26 ms 43360 KB Output is correct
6 Correct 23 ms 43280 KB Output is correct
7 Correct 23 ms 43352 KB Output is correct
8 Correct 24 ms 43348 KB Output is correct
9 Correct 23 ms 43348 KB Output is correct
10 Correct 26 ms 43248 KB Output is correct
11 Correct 21 ms 43348 KB Output is correct
12 Correct 23 ms 43340 KB Output is correct
13 Correct 25 ms 43400 KB Output is correct
14 Correct 23 ms 43280 KB Output is correct
15 Correct 23 ms 43348 KB Output is correct
16 Correct 23 ms 43284 KB Output is correct
17 Correct 22 ms 43280 KB Output is correct
18 Correct 23 ms 43248 KB Output is correct
19 Correct 23 ms 43276 KB Output is correct
20 Correct 27 ms 43340 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43348 KB Output is correct
2 Correct 22 ms 43364 KB Output is correct
3 Correct 25 ms 43324 KB Output is correct
4 Correct 23 ms 43360 KB Output is correct
5 Correct 26 ms 43360 KB Output is correct
6 Correct 23 ms 43280 KB Output is correct
7 Correct 23 ms 43352 KB Output is correct
8 Correct 24 ms 43348 KB Output is correct
9 Correct 23 ms 43348 KB Output is correct
10 Correct 26 ms 43248 KB Output is correct
11 Correct 21 ms 43348 KB Output is correct
12 Correct 23 ms 43340 KB Output is correct
13 Correct 25 ms 43400 KB Output is correct
14 Correct 23 ms 43280 KB Output is correct
15 Correct 23 ms 43348 KB Output is correct
16 Correct 23 ms 43284 KB Output is correct
17 Correct 22 ms 43280 KB Output is correct
18 Correct 23 ms 43248 KB Output is correct
19 Correct 23 ms 43276 KB Output is correct
20 Correct 27 ms 43340 KB Output is correct
21 Correct 25 ms 43316 KB Output is correct
22 Correct 24 ms 43348 KB Output is correct
23 Correct 22 ms 43420 KB Output is correct
24 Correct 24 ms 43408 KB Output is correct
25 Correct 25 ms 43328 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 45868 KB Output is correct
2 Correct 59 ms 46940 KB Output is correct
3 Correct 48 ms 45848 KB Output is correct
4 Correct 53 ms 46732 KB Output is correct
5 Correct 50 ms 45788 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 48468 KB Output is correct
2 Correct 56 ms 48504 KB Output is correct
3 Correct 62 ms 48332 KB Output is correct
4 Correct 60 ms 48544 KB Output is correct
5 Correct 56 ms 48360 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 48644 KB Output is correct
2 Correct 60 ms 48576 KB Output is correct
3 Correct 60 ms 48512 KB Output is correct
4 Correct 60 ms 48692 KB Output is correct
5 Correct 63 ms 48712 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43348 KB Output is correct
2 Correct 22 ms 43364 KB Output is correct
3 Correct 25 ms 43324 KB Output is correct
4 Correct 23 ms 43360 KB Output is correct
5 Correct 26 ms 43360 KB Output is correct
6 Correct 23 ms 43280 KB Output is correct
7 Correct 23 ms 43352 KB Output is correct
8 Correct 24 ms 43348 KB Output is correct
9 Correct 23 ms 43348 KB Output is correct
10 Correct 26 ms 43248 KB Output is correct
11 Correct 46 ms 45868 KB Output is correct
12 Correct 59 ms 46940 KB Output is correct
13 Correct 48 ms 45848 KB Output is correct
14 Correct 53 ms 46732 KB Output is correct
15 Correct 50 ms 45788 KB Output is correct
16 Correct 43 ms 45720 KB Output is correct
17 Correct 58 ms 47028 KB Output is correct
18 Correct 65 ms 47000 KB Output is correct
19 Correct 40 ms 45716 KB Output is correct
20 Correct 59 ms 46976 KB Output is correct
21 Correct 42 ms 45768 KB Output is correct
22 Correct 55 ms 46800 KB Output is correct
23 Correct 45 ms 45972 KB Output is correct
24 Correct 53 ms 46764 KB Output is correct
25 Correct 40 ms 45900 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43348 KB Output is correct
2 Correct 22 ms 43364 KB Output is correct
3 Correct 25 ms 43324 KB Output is correct
4 Correct 23 ms 43360 KB Output is correct
5 Correct 26 ms 43360 KB Output is correct
6 Correct 23 ms 43280 KB Output is correct
7 Correct 23 ms 43352 KB Output is correct
8 Correct 24 ms 43348 KB Output is correct
9 Correct 23 ms 43348 KB Output is correct
10 Correct 26 ms 43248 KB Output is correct
11 Correct 21 ms 43348 KB Output is correct
12 Correct 23 ms 43340 KB Output is correct
13 Correct 25 ms 43400 KB Output is correct
14 Correct 23 ms 43280 KB Output is correct
15 Correct 23 ms 43348 KB Output is correct
16 Correct 23 ms 43284 KB Output is correct
17 Correct 22 ms 43280 KB Output is correct
18 Correct 23 ms 43248 KB Output is correct
19 Correct 23 ms 43276 KB Output is correct
20 Correct 27 ms 43340 KB Output is correct
21 Correct 25 ms 43316 KB Output is correct
22 Correct 24 ms 43348 KB Output is correct
23 Correct 22 ms 43420 KB Output is correct
24 Correct 24 ms 43408 KB Output is correct
25 Correct 25 ms 43328 KB Output is correct
26 Correct 46 ms 45868 KB Output is correct
27 Correct 59 ms 46940 KB Output is correct
28 Correct 48 ms 45848 KB Output is correct
29 Correct 53 ms 46732 KB Output is correct
30 Correct 50 ms 45788 KB Output is correct
31 Correct 55 ms 48468 KB Output is correct
32 Correct 56 ms 48504 KB Output is correct
33 Correct 62 ms 48332 KB Output is correct
34 Correct 60 ms 48544 KB Output is correct
35 Correct 56 ms 48360 KB Output is correct
36 Correct 62 ms 48644 KB Output is correct
37 Correct 60 ms 48576 KB Output is correct
38 Correct 60 ms 48512 KB Output is correct
39 Correct 60 ms 48692 KB Output is correct
40 Correct 63 ms 48712 KB Output is correct
41 Correct 43 ms 45720 KB Output is correct
42 Correct 58 ms 47028 KB Output is correct
43 Correct 65 ms 47000 KB Output is correct
44 Correct 40 ms 45716 KB Output is correct
45 Correct 59 ms 46976 KB Output is correct
46 Correct 42 ms 45768 KB Output is correct
47 Correct 55 ms 46800 KB Output is correct
48 Correct 45 ms 45972 KB Output is correct
49 Correct 53 ms 46764 KB Output is correct
50 Correct 40 ms 45900 KB Output is correct
51 Correct 68 ms 47308 KB Output is correct
52 Correct 99 ms 48096 KB Output is correct
53 Correct 65 ms 47320 KB Output is correct
54 Correct 77 ms 48108 KB Output is correct
55 Correct 65 ms 47268 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43348 KB Output is correct
2 Correct 22 ms 43364 KB Output is correct
3 Correct 25 ms 43324 KB Output is correct
4 Correct 23 ms 43360 KB Output is correct
5 Correct 26 ms 43360 KB Output is correct
6 Correct 23 ms 43280 KB Output is correct
7 Correct 23 ms 43352 KB Output is correct
8 Correct 24 ms 43348 KB Output is correct
9 Correct 23 ms 43348 KB Output is correct
10 Correct 26 ms 43248 KB Output is correct
11 Correct 21 ms 43348 KB Output is correct
12 Correct 23 ms 43340 KB Output is correct
13 Correct 25 ms 43400 KB Output is correct
14 Correct 23 ms 43280 KB Output is correct
15 Correct 23 ms 43348 KB Output is correct
16 Correct 23 ms 43284 KB Output is correct
17 Correct 22 ms 43280 KB Output is correct
18 Correct 23 ms 43248 KB Output is correct
19 Correct 23 ms 43276 KB Output is correct
20 Correct 27 ms 43340 KB Output is correct
21 Correct 25 ms 43316 KB Output is correct
22 Correct 24 ms 43348 KB Output is correct
23 Correct 22 ms 43420 KB Output is correct
24 Correct 24 ms 43408 KB Output is correct
25 Correct 25 ms 43328 KB Output is correct
26 Correct 46 ms 45868 KB Output is correct
27 Correct 59 ms 46940 KB Output is correct
28 Correct 48 ms 45848 KB Output is correct
29 Correct 53 ms 46732 KB Output is correct
30 Correct 50 ms 45788 KB Output is correct
31 Correct 55 ms 48468 KB Output is correct
32 Correct 56 ms 48504 KB Output is correct
33 Correct 62 ms 48332 KB Output is correct
34 Correct 60 ms 48544 KB Output is correct
35 Correct 56 ms 48360 KB Output is correct
36 Correct 62 ms 48644 KB Output is correct
37 Correct 60 ms 48576 KB Output is correct
38 Correct 60 ms 48512 KB Output is correct
39 Correct 60 ms 48692 KB Output is correct
40 Correct 63 ms 48712 KB Output is correct
41 Correct 43 ms 45720 KB Output is correct
42 Correct 58 ms 47028 KB Output is correct
43 Correct 65 ms 47000 KB Output is correct
44 Correct 40 ms 45716 KB Output is correct
45 Correct 59 ms 46976 KB Output is correct
46 Correct 42 ms 45768 KB Output is correct
47 Correct 55 ms 46800 KB Output is correct
48 Correct 45 ms 45972 KB Output is correct
49 Correct 53 ms 46764 KB Output is correct
50 Correct 40 ms 45900 KB Output is correct
51 Correct 68 ms 47308 KB Output is correct
52 Correct 99 ms 48096 KB Output is correct
53 Correct 65 ms 47320 KB Output is correct
54 Correct 77 ms 48108 KB Output is correct
55 Correct 65 ms 47268 KB Output is correct
56 Correct 671 ms 83468 KB Output is correct
57 Correct 675 ms 83936 KB Output is correct
58 Correct 611 ms 81356 KB Output is correct
59 Correct 651 ms 82728 KB Output is correct
60 Correct 771 ms 84660 KB Output is correct