oj.uz

Submission #884071

# Submission time Handle Problem Language Result Execution time Memory
884071 2023-12-06T15:28:23 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 6498 ms 56148 KB 
#include <bits/stdc++.h>

using namespace std;

int aint[8000 * 4 + 5];
int ain2[50000 * 4 + 2][102];
int lazy[50000 * 4 + 2][102];
const int INF = 1e5;

void update(int nod, int st, int dr, int poz, int val)
{
    if(st == dr)
    {
        aint[nod] += val;
        return;
    }

    int mij = (st + dr) / 2;
    if(poz <= mij) update(nod * 2, st, mij, poz, val);
    else update(nod * 2 + 1, mij + 1, dr, poz, val);
    aint[nod] = max(aint[nod * 2], aint[nod * 2 + 1]);
}

void propagate(int nod, int id)
{
    ain2[nod * 2][id] += lazy[nod][id];
    ain2[nod * 2 + 1][id] += lazy[nod][id];
    lazy[nod * 2][id] += lazy[nod][id];
    lazy[nod * 2 + 1][id] += lazy[nod][id];
    lazy[nod][id] = 0;
}

void update2(int nod, int st, int dr, int le, int ri, int val, int id)
{
    if(le > ri)
        return;

    if(st == le && dr == ri)
    {
        ain2[nod][id] += val;
        lazy[nod][id] += val;
        return;
    }

    propagate(nod, id);
    int mij = (st + dr) / 2;
    update2(nod * 2, st, mij, le, min(ri, mij), val, id);
    update2(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri, val, id);
    ain2[nod][id] = max(ain2[nod * 2][id], ain2[nod * 2 + 1][id]);
}


vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
    int n = a.size();
    int q = x.size();
    if(n <= 8000 && q <= 8000)
    {
        int rez = 0;
        for(int i = 0; i < n; i++)
            for(int j = i - 1; j >= 0; j--)
                if(a[j] > a[i])
                    update(1, 1, n, i + 1, 1);
        vector<int> fin;
        for(int i = 0; i < q; i++)
        {
            //cout<<rez<<" zzzz\n";
            for(int j = x[i] + 1; j < n; j++)
            {
                if(a[x[i]] > a[j])
                    update(1, 1, n, j + 1, -1);
                if(v[i] > a[j])
                    update(1, 1, n, j + 1, 1);
            }

            for(int j = x[i] - 1; j >= 0; j--)
            {
                if(a[j] > a[x[i]])
                    update(1, 1, n, x[i] + 1, -1);
                if(a[j] > v[i])
                    update(1, 1, n, x[i] + 1, 1);
            }

            a[x[i]] = v[i];
            fin.push_back(aint[1]);
        }

        return fin;
    }
    else
    {
        for(int i = 1; i <= 100; i++)
            update2(1, 1, n, 1, n, -INF, i);

        for(int i = 0; i < n; i++)
        {
            update2(1, 1, n, i + 1, i + 1, INF, a[i]);
            for(int val = a[i] - 1; val >= 1; val--)
            {
                update2(1, 1, n, i + 2, n, 1, val);
            }
        }

        vector<int> fin;
        for(int i = 0; i < q; i++)
        {
            update2(1, 1, n, x[i] + 1, x[i] + 1, -INF, a[x[i]]);
            update2(1, 1, n, x[i] + 1, x[i] + 1, INF, v[i]);
            for(int val = a[x[i]] - 1; val >= 1; val--)
            {
                update2(1, 1, n, x[i] + 2, n, -1, val);
            }

            for(int val = v[i] - 1; val >= 1; val--)
            {
                update2(1, 1, n, x[i] + 2, n, 1, val);
            }

            int rez = 0;
            for(int j = 1; j <= 100; j++)
                rez = max(rez, ain2[1][j]);
            fin.push_back(rez);
        }

        return fin;
    }

}

/*int main()
{
    int n;
    cin>>n;
    vector<int> read;
    for(int i = 1; i <= n; i++)
    {
        int a;
        cin>>a;
        read.push_back(a);
    }

    vector<int> q1, q2;
    int q;
    cin>>q;
    for(int i = 1; i <= q; i++)
    {
        int a, b;
        cin>>a>>b;
        q1.push_back(a);
        q2.push_back(b);
    }

    vector<int> rez = countScans(read, q1, q2);
    for(auto it : rez)
        cout<<it<<'\n';
    return 0;
}*/

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:59:13: warning: unused variable 'rez' [-Wunused-variable]
   59 |         int rez = 0;
      |             ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 600 KB Output is correct
2 Correct 40 ms 348 KB Output is correct
3 Correct 280 ms 488 KB Output is correct
4 Correct 268 ms 488 KB Output is correct
5 Correct 142 ms 348 KB Output is correct
6 Correct 158 ms 344 KB Output is correct
7 Correct 144 ms 344 KB Output is correct
8 Correct 139 ms 504 KB Output is correct
9 Correct 143 ms 600 KB Output is correct
10 Correct 332 ms 504 KB Output is correct
11 Correct 328 ms 512 KB Output is correct
12 Correct 335 ms 488 KB Output is correct
13 Correct 291 ms 504 KB Output is correct
14 Correct 323 ms 740 KB Output is correct
15 Correct 291 ms 348 KB Output is correct
16 Correct 277 ms 748 KB Output is correct
17 Correct 245 ms 504 KB Output is correct
18 Correct 248 ms 492 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 600 KB Output is correct
2 Correct 40 ms 348 KB Output is correct
3 Correct 280 ms 488 KB Output is correct
4 Correct 268 ms 488 KB Output is correct
5 Correct 142 ms 348 KB Output is correct
6 Correct 158 ms 344 KB Output is correct
7 Correct 144 ms 344 KB Output is correct
8 Correct 139 ms 504 KB Output is correct
9 Correct 143 ms 600 KB Output is correct
10 Correct 332 ms 504 KB Output is correct
11 Correct 328 ms 512 KB Output is correct
12 Correct 335 ms 488 KB Output is correct
13 Correct 291 ms 504 KB Output is correct
14 Correct 323 ms 740 KB Output is correct
15 Correct 291 ms 348 KB Output is correct
16 Correct 277 ms 748 KB Output is correct
17 Correct 245 ms 504 KB Output is correct
18 Correct 248 ms 492 KB Output is correct
19 Correct 3848 ms 952 KB Output is correct
20 Correct 5067 ms 940 KB Output is correct
21 Correct 2603 ms 744 KB Output is correct
22 Correct 2579 ms 644 KB Output is correct
23 Correct 6498 ms 676 KB Output is correct
24 Correct 6279 ms 956 KB Output is correct
25 Correct 5665 ms 932 KB Output is correct
26 Correct 5538 ms 744 KB Output is correct
27 Correct 4936 ms 740 KB Output is correct
28 Correct 4932 ms 740 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 600 KB Output is correct
2 Correct 40 ms 348 KB Output is correct
3 Correct 280 ms 488 KB Output is correct
4 Correct 268 ms 488 KB Output is correct
5 Correct 142 ms 348 KB Output is correct
6 Correct 158 ms 344 KB Output is correct
7 Correct 144 ms 344 KB Output is correct
8 Correct 139 ms 504 KB Output is correct
9 Correct 143 ms 600 KB Output is correct
10 Correct 332 ms 504 KB Output is correct
11 Correct 328 ms 512 KB Output is correct
12 Correct 335 ms 488 KB Output is correct
13 Correct 291 ms 504 KB Output is correct
14 Correct 323 ms 740 KB Output is correct
15 Correct 291 ms 348 KB Output is correct
16 Correct 277 ms 748 KB Output is correct
17 Correct 245 ms 504 KB Output is correct
18 Correct 248 ms 492 KB Output is correct
19 Correct 3848 ms 952 KB Output is correct
20 Correct 5067 ms 940 KB Output is correct
21 Correct 2603 ms 744 KB Output is correct
22 Correct 2579 ms 644 KB Output is correct
23 Correct 6498 ms 676 KB Output is correct
24 Correct 6279 ms 956 KB Output is correct
25 Correct 5665 ms 932 KB Output is correct
26 Correct 5538 ms 744 KB Output is correct
27 Correct 4936 ms 740 KB Output is correct
28 Correct 4932 ms 740 KB Output is correct
29 Incorrect 263 ms 56148 KB Output isn't correct
30 Halted 0 ms 0 KB -