oj.uz

Submission #1116659

# Submission time Handle Problem Language Result Execution time Memory
1116659 2024-11-22T06:07:39 Z jkb_gryz Bubble Sort 2 (JOI18_bubblesort2) C++14
100 / 100
 3246 ms 138544 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"
 
using namespace std;
#define ll long long
#define para pair<ll, ll>
 
const int base = 1<<20;
const ll INF = 1e18+7;
const ll MAXN = 1e6+7;
 
ll tree[base<<1];
ll lazy[base<<1];
 
void push(ll v){
    lazy[2*v] += lazy[v];
    lazy[2*v+1] += lazy[v];
    
    tree[2*v] += lazy[v];
    tree[2*v+1] += lazy[v];
 
    lazy[v] = 0;
}
 
ll p, k;
ll val;
ll smaller[MAXN];
 
void update(ll v, ll l, ll r){
    if(l > k || r < p) return;
    if(p <= l && r <= k){
        tree[v] += val;
        lazy[v] += val;
    }
    else{
        ll mid = (l+r)/2;
 
        push(v);
 
        update(2*v, l, mid);
        update(2*v+1, mid+1, r);
 
        tree[v] = max(tree[2*v], tree[2*v+1]);
    }
}
 
ll query(ll v, ll l, ll r){
    if(l > k || r < p) return -INF;
    if(p <= l && r <= k){
        return tree[v];
    }
    else{
        ll mid = (l+r)/2;
 
        push(v);
 
        auto lQ = query(2*v, l, mid);
        auto rQ = query(2*v+1, mid+1, r);
        return max(lQ, rQ);
    }
}
 
 
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){     
    int n = A.size();
	int Q = X.size();
	vector<int> res(Q);
 
    vector<ll> skalowanie;
    for(auto i : A)
        skalowanie.push_back(i);

    for(auto i : V)
        skalowanie.push_back(i);
    
    sort(skalowanie.begin(), skalowanie.end());
    map<ll, ll> skalowanie2;
    ll prev = 0;
    for(ll i = 0; i < skalowanie.size(); ++i){
        if(skalowanie2[skalowanie[i]] == 0) skalowanie2[skalowanie[i]] = i+1, prev = i;
        smaller[i+1] = prev;
    }
    ll id = skalowanie.size()+7;

    p = 0, k = id;
    val = -INF;
    update(1, 1, id);
    
    for(ll i = 0; i < n; ++i){
        A[i] = skalowanie2[A[i]]++;
        p = 0, k = smaller[A[i]];
        val = 1;
        update(1, 1, id);
        p = k = A[i];
        val = INF + i; 
        update(1, 1, id);
    }

    for(ll i = 0; i < Q; ++i){
        p = 0, k = smaller[A[X[i]]];
        val = -1;
        update(1, 1, id);
        p = k = A[X[i]];
        val = -INF;
        update(1, 1, id);

        A[X[i]] = skalowanie2[V[i]]++;

        p = 0, k = smaller[A[X[i]]];
        val = 1;
        update(1, 1, id);
        p = k = A[X[i]];
        val = INF + X[i];
        update(1, 1, id);
        p = 0, k = id;
        res[i] = query(1, 1, id) - n + 1;
    }
 
	return res;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:79:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(ll i = 0; i < skalowanie.size(); ++i){
      |                   ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4432 KB Output is correct
2 Correct 4 ms 4688 KB Output is correct
3 Correct 6 ms 4944 KB Output is correct
4 Correct 5 ms 4924 KB Output is correct
5 Correct 5 ms 4944 KB Output is correct
6 Correct 5 ms 4944 KB Output is correct
7 Correct 5 ms 4944 KB Output is correct
8 Correct 5 ms 4944 KB Output is correct
9 Correct 5 ms 4808 KB Output is correct
10 Correct 4 ms 4856 KB Output is correct
11 Correct 4 ms 4688 KB Output is correct
12 Correct 4 ms 4688 KB Output is correct
13 Correct 4 ms 4688 KB Output is correct
14 Correct 5 ms 4856 KB Output is correct
15 Correct 5 ms 4688 KB Output is correct
16 Correct 4 ms 4688 KB Output is correct
17 Correct 4 ms 4688 KB Output is correct
18 Correct 4 ms 4688 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4432 KB Output is correct
2 Correct 4 ms 4688 KB Output is correct
3 Correct 6 ms 4944 KB Output is correct
4 Correct 5 ms 4924 KB Output is correct
5 Correct 5 ms 4944 KB Output is correct
6 Correct 5 ms 4944 KB Output is correct
7 Correct 5 ms 4944 KB Output is correct
8 Correct 5 ms 4944 KB Output is correct
9 Correct 5 ms 4808 KB Output is correct
10 Correct 4 ms 4856 KB Output is correct
11 Correct 4 ms 4688 KB Output is correct
12 Correct 4 ms 4688 KB Output is correct
13 Correct 4 ms 4688 KB Output is correct
14 Correct 5 ms 4856 KB Output is correct
15 Correct 5 ms 4688 KB Output is correct
16 Correct 4 ms 4688 KB Output is correct
17 Correct 4 ms 4688 KB Output is correct
18 Correct 4 ms 4688 KB Output is correct
19 Correct 17 ms 5968 KB Output is correct
20 Correct 19 ms 6096 KB Output is correct
21 Correct 18 ms 6224 KB Output is correct
22 Correct 18 ms 6096 KB Output is correct
23 Correct 17 ms 5968 KB Output is correct
24 Correct 17 ms 6000 KB Output is correct
25 Correct 20 ms 6224 KB Output is correct
26 Correct 17 ms 5968 KB Output is correct
27 Correct 20 ms 5840 KB Output is correct
28 Correct 18 ms 5712 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5844 KB Output is correct
2 Correct 40 ms 7864 KB Output is correct
3 Correct 73 ms 10940 KB Output is correct
4 Correct 78 ms 11000 KB Output is correct
5 Correct 71 ms 10888 KB Output is correct
6 Correct 74 ms 10940 KB Output is correct
7 Correct 73 ms 10940 KB Output is correct
8 Correct 74 ms 10936 KB Output is correct
9 Correct 81 ms 12476 KB Output is correct
10 Correct 72 ms 11196 KB Output is correct
11 Correct 63 ms 11196 KB Output is correct
12 Correct 69 ms 12476 KB Output is correct
13 Correct 63 ms 11196 KB Output is correct
14 Correct 73 ms 10940 KB Output is correct
15 Correct 65 ms 11048 KB Output is correct
16 Correct 72 ms 11204 KB Output is correct
17 Correct 65 ms 11000 KB Output is correct
18 Correct 61 ms 10948 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4432 KB Output is correct
2 Correct 4 ms 4688 KB Output is correct
3 Correct 6 ms 4944 KB Output is correct
4 Correct 5 ms 4924 KB Output is correct
5 Correct 5 ms 4944 KB Output is correct
6 Correct 5 ms 4944 KB Output is correct
7 Correct 5 ms 4944 KB Output is correct
8 Correct 5 ms 4944 KB Output is correct
9 Correct 5 ms 4808 KB Output is correct
10 Correct 4 ms 4856 KB Output is correct
11 Correct 4 ms 4688 KB Output is correct
12 Correct 4 ms 4688 KB Output is correct
13 Correct 4 ms 4688 KB Output is correct
14 Correct 5 ms 4856 KB Output is correct
15 Correct 5 ms 4688 KB Output is correct
16 Correct 4 ms 4688 KB Output is correct
17 Correct 4 ms 4688 KB Output is correct
18 Correct 4 ms 4688 KB Output is correct
19 Correct 17 ms 5968 KB Output is correct
20 Correct 19 ms 6096 KB Output is correct
21 Correct 18 ms 6224 KB Output is correct
22 Correct 18 ms 6096 KB Output is correct
23 Correct 17 ms 5968 KB Output is correct
24 Correct 17 ms 6000 KB Output is correct
25 Correct 20 ms 6224 KB Output is correct
26 Correct 17 ms 5968 KB Output is correct
27 Correct 20 ms 5840 KB Output is correct
28 Correct 18 ms 5712 KB Output is correct
29 Correct 14 ms 5844 KB Output is correct
30 Correct 40 ms 7864 KB Output is correct
31 Correct 73 ms 10940 KB Output is correct
32 Correct 78 ms 11000 KB Output is correct
33 Correct 71 ms 10888 KB Output is correct
34 Correct 74 ms 10940 KB Output is correct
35 Correct 73 ms 10940 KB Output is correct
36 Correct 74 ms 10936 KB Output is correct
37 Correct 81 ms 12476 KB Output is correct
38 Correct 72 ms 11196 KB Output is correct
39 Correct 63 ms 11196 KB Output is correct
40 Correct 69 ms 12476 KB Output is correct
41 Correct 63 ms 11196 KB Output is correct
42 Correct 73 ms 10940 KB Output is correct
43 Correct 65 ms 11048 KB Output is correct
44 Correct 72 ms 11204 KB Output is correct
45 Correct 65 ms 11000 KB Output is correct
46 Correct 61 ms 10948 KB Output is correct
47 Correct 720 ms 47680 KB Output is correct
48 Correct 2760 ms 130216 KB Output is correct
49 Correct 2978 ms 138412 KB Output is correct
50 Correct 3246 ms 138408 KB Output is correct
51 Correct 3077 ms 138408 KB Output is correct
52 Correct 2791 ms 138408 KB Output is correct
53 Correct 3238 ms 138408 KB Output is correct
54 Correct 2745 ms 138464 KB Output is correct
55 Correct 2868 ms 138408 KB Output is correct
56 Correct 2811 ms 138544 KB Output is correct
57 Correct 2796 ms 138492 KB Output is correct
58 Correct 2791 ms 138408 KB Output is correct
59 Correct 2644 ms 129260 KB Output is correct
60 Correct 2383 ms 129336 KB Output is correct
61 Correct 2246 ms 129396 KB Output is correct
62 Correct 2559 ms 125352 KB Output is correct
63 Correct 2500 ms 125352 KB Output is correct
64 Correct 2315 ms 125320 KB Output is correct
65 Correct 2246 ms 121252 KB Output is correct
66 Correct 2418 ms 121180 KB Output is correct
67 Correct 2073 ms 121260 KB Output is correct