oj.uz

Submission #894658

# Submission time Handle Problem Language Result Execution time Memory
894658 2023-12-28T15:41:30 Z lunaTu Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 3092 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#include "bubblesort2.h"
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int N = 5e4 + 1;
int A[N];
set<int> s;
map<int, ordered_set> d;
map<int, int> ans;

int add(int i, int x) {
    int p = A[i];

    d[p].erase(i);
    ans[p] = 0;
    d[x].insert(i);
    ans[x] = 0;
    s.insert(x);

    if (d[p].empty()) {
        s.erase(p);
    }

    int mx = 0;
    int j1 = *d[x].rbegin(), j2 = *d[p].rbegin();

    // 3 2 1 4
    for (auto e : s) {

        int l = *d[e].begin(), r = *d[e].rbegin();

        if (e < p && r > i) ans[e]--;
        if (e < x && r > i) ans[e]++;

        if (!d[p].empty() && e > p) {
            ans[p] += d[e].order_of_key(j2);
        }
        if (e > x) {
            ans[x] += d[e].order_of_key(j1);
        }
        mx = max(mx, ans[e]);
    }

    A[i] = x;
    mx = max(mx, max(ans[p], ans[x]));
    return mx;
}

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v){
    int n = a.size();
    for (int i = 0; i < n; i++) {
        int w = add(i, a[i]);
    }

	int q = x.size();

	vector<int> answer(q);

	for (int j = 0; j < q; j++) {
		answer[j] = add(x[j], v[j]);
	}

	return answer;
}

Compilation message

bubblesort2.cpp: In function 'int add(int, int)':
bubblesort2.cpp:45:13: warning: unused variable 'l' [-Wunused-variable]
   45 |         int l = *d[e].begin(), r = *d[e].rbegin();
      |             ^
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:67:13: warning: unused variable 'w' [-Wunused-variable]
   67 |         int w = add(i, a[i]);
      |             ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 668 KB Output is correct
2 Correct 189 ms 832 KB Output is correct
3 Correct 1190 ms 1260 KB Output is correct
4 Correct 1184 ms 1532 KB Output is correct
5 Correct 1119 ms 1436 KB Output is correct
6 Correct 1054 ms 1320 KB Output is correct
7 Correct 1117 ms 1436 KB Output is correct
8 Correct 1086 ms 1464 KB Output is correct
9 Correct 1131 ms 1240 KB Output is correct
10 Correct 1190 ms 1268 KB Output is correct
11 Correct 1210 ms 1536 KB Output is correct
12 Correct 1203 ms 1372 KB Output is correct
13 Correct 1148 ms 1496 KB Output is correct
14 Correct 1209 ms 1628 KB Output is correct
15 Correct 1153 ms 1424 KB Output is correct
16 Correct 1129 ms 1364 KB Output is correct
17 Correct 1131 ms 1416 KB Output is correct
18 Correct 1124 ms 1268 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 668 KB Output is correct
2 Correct 189 ms 832 KB Output is correct
3 Correct 1190 ms 1260 KB Output is correct
4 Correct 1184 ms 1532 KB Output is correct
5 Correct 1119 ms 1436 KB Output is correct
6 Correct 1054 ms 1320 KB Output is correct
7 Correct 1117 ms 1436 KB Output is correct
8 Correct 1086 ms 1464 KB Output is correct
9 Correct 1131 ms 1240 KB Output is correct
10 Correct 1190 ms 1268 KB Output is correct
11 Correct 1210 ms 1536 KB Output is correct
12 Correct 1203 ms 1372 KB Output is correct
13 Correct 1148 ms 1496 KB Output is correct
14 Correct 1209 ms 1628 KB Output is correct
15 Correct 1153 ms 1424 KB Output is correct
16 Correct 1129 ms 1364 KB Output is correct
17 Correct 1131 ms 1416 KB Output is correct
18 Correct 1124 ms 1268 KB Output is correct
19 Execution timed out 9011 ms 3092 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 668 KB Output is correct
2 Correct 189 ms 832 KB Output is correct
3 Correct 1190 ms 1260 KB Output is correct
4 Correct 1184 ms 1532 KB Output is correct
5 Correct 1119 ms 1436 KB Output is correct
6 Correct 1054 ms 1320 KB Output is correct
7 Correct 1117 ms 1436 KB Output is correct
8 Correct 1086 ms 1464 KB Output is correct
9 Correct 1131 ms 1240 KB Output is correct
10 Correct 1190 ms 1268 KB Output is correct
11 Correct 1210 ms 1536 KB Output is correct
12 Correct 1203 ms 1372 KB Output is correct
13 Correct 1148 ms 1496 KB Output is correct
14 Correct 1209 ms 1628 KB Output is correct
15 Correct 1153 ms 1424 KB Output is correct
16 Correct 1129 ms 1364 KB Output is correct
17 Correct 1131 ms 1416 KB Output is correct
18 Correct 1124 ms 1268 KB Output is correct
19 Execution timed out 9011 ms 3092 KB Time limit exceeded
20 Halted 0 ms 0 KB -