oj.uz

Submission #514547

# Submission time Handle Problem Language Result Execution time Memory
514547 2022-01-18T09:01:41 Z Vladth11 Bubble Sort 2 (JOI18_bubblesort2) C++14
100 / 100
 4678 ms 121724 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#include "bubblesort2.h"

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 10000001;
const ll VMAX = 21;
const ll INF = 2e9;
const ll MOD = 1000000007;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 60;

int n;

class AINT{
public:
    int aint[NMAX], lazy[NMAX];
    void propaga(int node, int st, int dr){
        if(st != dr)
        {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        aint[node] += lazy[node];
        lazy[node] = 0;
    }
    void update(int node, int st, int dr, int a, int b, int val){
        propaga(node, st, dr);
        if(a > b)
            return;
        if(a <= st && dr <= b){
            lazy[node] += val;
            return;
        }
        int mid = (st + dr) / 2;
        if(a <= mid)
            update(node * 2, st, mid, a, b, val);
        if(b > mid)
            update(node * 2 + 1, mid + 1, dr, a, b, val);
        propaga(node * 2, st, mid);
        propaga(node * 2 + 1, mid + 1, dr);
        aint[node] = max(aint[node * 2], aint[node * 2 + 1]);
    }
    int maxim(){
        propaga(1, 1, n);
        return aint[1];
    }
}st;

map <pii, int> mp;

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	int Q=X.size();
	vector<int> answer(Q);
    vector <pii> norm;
    swap(X, V); /// ups pare ca le-am incurcat
    for(int i = 0; i < A.size(); i++){
        norm.push_back({A[i], i + 1});
    }
    for(int i = 0; i < Q; i++){
        norm.push_back({X[i], V[i] + 1}); /// Grija aici la  + 1
    }
    sort(norm.begin(), norm.end());
    int cnt = 0;
    for(int i = 0; i < norm.size(); i++){
        if(i == 0 || norm[i] != norm[i - 1])
            cnt++;
        mp[norm[i]] = cnt;
    }
    n = cnt;
    for(int i = 1; i <= n; i++){
        st.update(1, 1, n, i, i, -INF);
    }
    for(int i = 0; i < A.size(); i++){
        pii x = {A[i], i + 1};
        int poz = mp[x];
        st.update(1, 1, n, poz, poz, INF);
        st.update(1, 1, n, poz, poz, i + 1);
        st.update(1, 1, n, poz + 1, n, -1); /// sortedPosition creste cu 1, deci contributia e -1
    }
    for(int i = 0; i < Q; i++){
        pii x = {A[V[i]], V[i] + 1};
        A[V[i]] = X[i];
        int poz = mp[x];
        st.update(1, 1, n, poz, poz, -INF);
        st.update(1, 1, n, poz, poz, -x.second);
        st.update(1, 1, n, poz + 1, n, 1);
        x = {A[V[i]], V[i] + 1};
        poz = mp[x];
        st.update(1, 1, n, poz, poz, INF);
        st.update(1, 1, n, poz, poz, x.second);
        st.update(1, 1, n, poz + 1, n, -1);
        answer[i] = st.maxim() - 1;
    }
	return answer;
}

Compilation message

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 6 ms 692 KB Output is correct
4 Correct 7 ms 692 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 688 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 7 ms 844 KB Output is correct
9 Correct 7 ms 792 KB Output is correct
10 Correct 6 ms 716 KB Output is correct
11 Correct 6 ms 716 KB Output is correct
12 Correct 9 ms 748 KB Output is correct
13 Correct 6 ms 696 KB Output is correct
14 Correct 6 ms 692 KB Output is correct
15 Correct 6 ms 716 KB Output is correct
16 Correct 6 ms 716 KB Output is correct
17 Correct 7 ms 672 KB Output is correct
18 Correct 6 ms 696 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 6 ms 692 KB Output is correct
4 Correct 7 ms 692 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 688 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 7 ms 844 KB Output is correct
9 Correct 7 ms 792 KB Output is correct
10 Correct 6 ms 716 KB Output is correct
11 Correct 6 ms 716 KB Output is correct
12 Correct 9 ms 748 KB Output is correct
13 Correct 6 ms 696 KB Output is correct
14 Correct 6 ms 692 KB Output is correct
15 Correct 6 ms 716 KB Output is correct
16 Correct 6 ms 716 KB Output is correct
17 Correct 7 ms 672 KB Output is correct
18 Correct 6 ms 696 KB Output is correct
19 Correct 26 ms 1960 KB Output is correct
20 Correct 31 ms 2120 KB Output is correct
21 Correct 28 ms 2108 KB Output is correct
22 Correct 29 ms 2192 KB Output is correct
23 Correct 29 ms 1972 KB Output is correct
24 Correct 26 ms 1972 KB Output is correct
25 Correct 38 ms 1956 KB Output is correct
26 Correct 26 ms 1964 KB Output is correct
27 Correct 25 ms 1840 KB Output is correct
28 Correct 28 ms 1952 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3428 KB Output is correct
2 Correct 125 ms 7336 KB Output is correct
3 Correct 243 ms 12008 KB Output is correct
4 Correct 259 ms 11956 KB Output is correct
5 Correct 254 ms 11976 KB Output is correct
6 Correct 253 ms 11876 KB Output is correct
7 Correct 264 ms 11824 KB Output is correct
8 Correct 290 ms 11932 KB Output is correct
9 Correct 241 ms 11844 KB Output is correct
10 Correct 181 ms 8244 KB Output is correct
11 Correct 177 ms 8240 KB Output is correct
12 Correct 176 ms 8196 KB Output is correct
13 Correct 168 ms 8268 KB Output is correct
14 Correct 173 ms 8372 KB Output is correct
15 Correct 167 ms 8272 KB Output is correct
16 Correct 160 ms 8232 KB Output is correct
17 Correct 174 ms 8268 KB Output is correct
18 Correct 178 ms 8244 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 6 ms 692 KB Output is correct
4 Correct 7 ms 692 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 688 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 7 ms 844 KB Output is correct
9 Correct 7 ms 792 KB Output is correct
10 Correct 6 ms 716 KB Output is correct
11 Correct 6 ms 716 KB Output is correct
12 Correct 9 ms 748 KB Output is correct
13 Correct 6 ms 696 KB Output is correct
14 Correct 6 ms 692 KB Output is correct
15 Correct 6 ms 716 KB Output is correct
16 Correct 6 ms 716 KB Output is correct
17 Correct 7 ms 672 KB Output is correct
18 Correct 6 ms 696 KB Output is correct
19 Correct 26 ms 1960 KB Output is correct
20 Correct 31 ms 2120 KB Output is correct
21 Correct 28 ms 2108 KB Output is correct
22 Correct 29 ms 2192 KB Output is correct
23 Correct 29 ms 1972 KB Output is correct
24 Correct 26 ms 1972 KB Output is correct
25 Correct 38 ms 1956 KB Output is correct
26 Correct 26 ms 1964 KB Output is correct
27 Correct 25 ms 1840 KB Output is correct
28 Correct 28 ms 1952 KB Output is correct
29 Correct 44 ms 3428 KB Output is correct
30 Correct 125 ms 7336 KB Output is correct
31 Correct 243 ms 12008 KB Output is correct
32 Correct 259 ms 11956 KB Output is correct
33 Correct 254 ms 11976 KB Output is correct
34 Correct 253 ms 11876 KB Output is correct
35 Correct 264 ms 11824 KB Output is correct
36 Correct 290 ms 11932 KB Output is correct
37 Correct 241 ms 11844 KB Output is correct
38 Correct 181 ms 8244 KB Output is correct
39 Correct 177 ms 8240 KB Output is correct
40 Correct 176 ms 8196 KB Output is correct
41 Correct 168 ms 8268 KB Output is correct
42 Correct 173 ms 8372 KB Output is correct
43 Correct 167 ms 8272 KB Output is correct
44 Correct 160 ms 8232 KB Output is correct
45 Correct 174 ms 8268 KB Output is correct
46 Correct 178 ms 8244 KB Output is correct
47 Correct 1066 ms 39320 KB Output is correct
48 Correct 4483 ms 112804 KB Output is correct
49 Correct 4623 ms 121476 KB Output is correct
50 Correct 4639 ms 121576 KB Output is correct
51 Correct 4472 ms 121552 KB Output is correct
52 Correct 4550 ms 121572 KB Output is correct
53 Correct 4510 ms 121648 KB Output is correct
54 Correct 4299 ms 121600 KB Output is correct
55 Correct 4678 ms 121724 KB Output is correct
56 Correct 4282 ms 121684 KB Output is correct
57 Correct 4588 ms 121632 KB Output is correct
58 Correct 4208 ms 121632 KB Output is correct
59 Correct 3783 ms 112548 KB Output is correct
60 Correct 3857 ms 112492 KB Output is correct
61 Correct 3624 ms 112516 KB Output is correct
62 Correct 3635 ms 108380 KB Output is correct
63 Correct 3720 ms 108420 KB Output is correct
64 Correct 3454 ms 108528 KB Output is correct
65 Correct 3344 ms 104400 KB Output is correct
66 Correct 3297 ms 104500 KB Output is correct
67 Correct 3349 ms 104500 KB Output is correct