oj.uz

Submission #884065

# Submission time Handle Problem Language Result Execution time Memory
884065 2023-12-06T15:20:38 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
60 / 100
 9000 ms 17528 KB 
#include "bubblesort2.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int , int> , null_type, less<pair<int , int>>, rb_tree_tag, tree_order_statistics_node_update> orderedSet;

std::vector<int> countScans(std::vector<int> a,std::vector<int> X,std::vector<int> V){
	int Q=X.size();
	int n = a.size();
	std::vector<int> answer(Q);

    priority_queue<int> q[101];

    orderedSet s;
    bool subtrask_penal = 1;
    for (int i = 0; i < n; i++)
    {
        s.insert ({a[i] , i});
        if (a[i] > 100) subtrask_penal = 0;
        else q[a[i]].push(i);
    }

    if (subtrask_penal) {
    for (int j = 0; j < Q; j++)
    {
        s.erase({a[X[j]] , X[j]});
        a[X[j]] = V[j];
        s.insert({a[X[j]] , X[j]});
        q[a[X[j]]].push(X[j]);
        for (int val = 1; val <= 100; val++)
        {
            while (q[val].size() && a[q[val].top()] != val) q[val].pop();
            if (q[val].size())
            {
                answer[j] = max(answer[j] , q[val].top() - (int)s.order_of_key({val, q[val].top()}));
            }
        }
    }
    }
    else {
    vector<pair<int, int> > crt;

    for (int i = 0; i < Q; i++)
    {
        a[X[i]] = V[i];
     //   cout << X[i] << ' ' << V[i] << '\n';
        vector<pair<int , int> > nou(n);
        for (int j = 0; j < n; j++)
        {
            nou[j] = {a[j] , j};
         //   cout << A[j] << ' ';
        }
        sort(nou.begin(), nou.end());
        for (int j = 0; j < n; j++)
        {
            answer[i] = max(answer[i] , nou[j].second - j);
        }
    }
    }

	return answer;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 348 KB Output is correct
2 Correct 30 ms 348 KB Output is correct
3 Correct 184 ms 600 KB Output is correct
4 Correct 181 ms 600 KB Output is correct
5 Correct 176 ms 604 KB Output is correct
6 Correct 110 ms 600 KB Output is correct
7 Correct 153 ms 600 KB Output is correct
8 Correct 168 ms 848 KB Output is correct
9 Correct 187 ms 604 KB Output is correct
10 Correct 104 ms 600 KB Output is correct
11 Correct 102 ms 600 KB Output is correct
12 Correct 106 ms 608 KB Output is correct
13 Correct 105 ms 612 KB Output is correct
14 Correct 103 ms 608 KB Output is correct
15 Correct 108 ms 608 KB Output is correct
16 Correct 103 ms 604 KB Output is correct
17 Correct 97 ms 604 KB Output is correct
18 Correct 89 ms 612 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 348 KB Output is correct
2 Correct 30 ms 348 KB Output is correct
3 Correct 184 ms 600 KB Output is correct
4 Correct 181 ms 600 KB Output is correct
5 Correct 176 ms 604 KB Output is correct
6 Correct 110 ms 600 KB Output is correct
7 Correct 153 ms 600 KB Output is correct
8 Correct 168 ms 848 KB Output is correct
9 Correct 187 ms 604 KB Output is correct
10 Correct 104 ms 600 KB Output is correct
11 Correct 102 ms 600 KB Output is correct
12 Correct 106 ms 608 KB Output is correct
13 Correct 105 ms 612 KB Output is correct
14 Correct 103 ms 608 KB Output is correct
15 Correct 108 ms 608 KB Output is correct
16 Correct 103 ms 604 KB Output is correct
17 Correct 97 ms 604 KB Output is correct
18 Correct 89 ms 612 KB Output is correct
19 Correct 2633 ms 1112 KB Output is correct
20 Correct 3490 ms 1188 KB Output is correct
21 Correct 2960 ms 1184 KB Output is correct
22 Correct 3330 ms 1188 KB Output is correct
23 Correct 1977 ms 1192 KB Output is correct
24 Correct 1978 ms 1196 KB Output is correct
25 Correct 1954 ms 1196 KB Output is correct
26 Correct 1968 ms 1192 KB Output is correct
27 Correct 1965 ms 1196 KB Output is correct
28 Correct 1993 ms 1208 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2652 KB Output is correct
2 Correct 168 ms 4196 KB Output is correct
3 Correct 343 ms 5620 KB Output is correct
4 Correct 331 ms 5544 KB Output is correct
5 Correct 335 ms 5820 KB Output is correct
6 Correct 320 ms 5692 KB Output is correct
7 Correct 348 ms 5456 KB Output is correct
8 Correct 335 ms 5500 KB Output is correct
9 Correct 304 ms 5324 KB Output is correct
10 Correct 182 ms 5584 KB Output is correct
11 Correct 209 ms 5416 KB Output is correct
12 Correct 225 ms 5340 KB Output is correct
13 Correct 182 ms 5096 KB Output is correct
14 Correct 203 ms 5180 KB Output is correct
15 Correct 196 ms 5180 KB Output is correct
16 Correct 184 ms 5132 KB Output is correct
17 Correct 184 ms 5068 KB Output is correct
18 Correct 181 ms 4988 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 348 KB Output is correct
2 Correct 30 ms 348 KB Output is correct
3 Correct 184 ms 600 KB Output is correct
4 Correct 181 ms 600 KB Output is correct
5 Correct 176 ms 604 KB Output is correct
6 Correct 110 ms 600 KB Output is correct
7 Correct 153 ms 600 KB Output is correct
8 Correct 168 ms 848 KB Output is correct
9 Correct 187 ms 604 KB Output is correct
10 Correct 104 ms 600 KB Output is correct
11 Correct 102 ms 600 KB Output is correct
12 Correct 106 ms 608 KB Output is correct
13 Correct 105 ms 612 KB Output is correct
14 Correct 103 ms 608 KB Output is correct
15 Correct 108 ms 608 KB Output is correct
16 Correct 103 ms 604 KB Output is correct
17 Correct 97 ms 604 KB Output is correct
18 Correct 89 ms 612 KB Output is correct
19 Correct 2633 ms 1112 KB Output is correct
20 Correct 3490 ms 1188 KB Output is correct
21 Correct 2960 ms 1184 KB Output is correct
22 Correct 3330 ms 1188 KB Output is correct
23 Correct 1977 ms 1192 KB Output is correct
24 Correct 1978 ms 1196 KB Output is correct
25 Correct 1954 ms 1196 KB Output is correct
26 Correct 1968 ms 1192 KB Output is correct
27 Correct 1965 ms 1196 KB Output is correct
28 Correct 1993 ms 1208 KB Output is correct
29 Correct 25 ms 2652 KB Output is correct
30 Correct 168 ms 4196 KB Output is correct
31 Correct 343 ms 5620 KB Output is correct
32 Correct 331 ms 5544 KB Output is correct
33 Correct 335 ms 5820 KB Output is correct
34 Correct 320 ms 5692 KB Output is correct
35 Correct 348 ms 5456 KB Output is correct
36 Correct 335 ms 5500 KB Output is correct
37 Correct 304 ms 5324 KB Output is correct
38 Correct 182 ms 5584 KB Output is correct
39 Correct 209 ms 5416 KB Output is correct
40 Correct 225 ms 5340 KB Output is correct
41 Correct 182 ms 5096 KB Output is correct
42 Correct 203 ms 5180 KB Output is correct
43 Correct 196 ms 5180 KB Output is correct
44 Correct 184 ms 5132 KB Output is correct
45 Correct 184 ms 5068 KB Output is correct
46 Correct 181 ms 4988 KB Output is correct
47 Execution timed out 9004 ms 17528 KB Time limit exceeded
48 Halted 0 ms 0 KB -