oj.uz

Submission #488773

# Submission time Handle Problem Language Result Execution time Memory
488773 2021-11-20T12:11:27 Z grt Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 2256 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

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

int n, q;
ordered_set S;
map<int,int>occ;

vi countScans(vi A, vi X, vi V) {
	n = (int)A.size(); q = (int)X.size();
	vi ans(q);
	for(int i = 0; i < q; ++i) {
		A[X[i]] = V[i];
		S.clear();
		occ.clear();
		ans[i] = 0;
		for(int j = 0; j < n; ++j) {
			int x = S.order_of_key({-A[j], -1});
			ans[i] = max(ans[i], x);
			S.insert({-A[j], occ[A[j]]++});
		}
	}
	return ans;	
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//cin >> n >> q;
	//vi A(n), X(q), V(q);
	//for(int i = 0; i < n; ++i) cin >> A[i];
	//for(int i = 0; i < q; ++i) cin >> X[i] >> V[i];
	//vi ans = countScans(A, X, V);
	//for(int x : ans) {
		//cout << x << "\n";
	//}
//}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 336 KB Output is correct
2 Correct 229 ms 400 KB Output is correct
3 Correct 1492 ms 612 KB Output is correct
4 Correct 1485 ms 592 KB Output is correct
5 Correct 1444 ms 592 KB Output is correct
6 Correct 1333 ms 608 KB Output is correct
7 Correct 1405 ms 592 KB Output is correct
8 Correct 1434 ms 592 KB Output is correct
9 Correct 1438 ms 592 KB Output is correct
10 Correct 1247 ms 604 KB Output is correct
11 Correct 1254 ms 592 KB Output is correct
12 Correct 1259 ms 592 KB Output is correct
13 Correct 1263 ms 592 KB Output is correct
14 Correct 1272 ms 592 KB Output is correct
15 Correct 1214 ms 712 KB Output is correct
16 Correct 1244 ms 592 KB Output is correct
17 Correct 1249 ms 592 KB Output is correct
18 Correct 1314 ms 592 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 336 KB Output is correct
2 Correct 229 ms 400 KB Output is correct
3 Correct 1492 ms 612 KB Output is correct
4 Correct 1485 ms 592 KB Output is correct
5 Correct 1444 ms 592 KB Output is correct
6 Correct 1333 ms 608 KB Output is correct
7 Correct 1405 ms 592 KB Output is correct
8 Correct 1434 ms 592 KB Output is correct
9 Correct 1438 ms 592 KB Output is correct
10 Correct 1247 ms 604 KB Output is correct
11 Correct 1254 ms 592 KB Output is correct
12 Correct 1259 ms 592 KB Output is correct
13 Correct 1263 ms 592 KB Output is correct
14 Correct 1272 ms 592 KB Output is correct
15 Correct 1214 ms 712 KB Output is correct
16 Correct 1244 ms 592 KB Output is correct
17 Correct 1249 ms 592 KB Output is correct
18 Correct 1314 ms 592 KB Output is correct
19 Execution timed out 9048 ms 1384 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9015 ms 2256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 336 KB Output is correct
2 Correct 229 ms 400 KB Output is correct
3 Correct 1492 ms 612 KB Output is correct
4 Correct 1485 ms 592 KB Output is correct
5 Correct 1444 ms 592 KB Output is correct
6 Correct 1333 ms 608 KB Output is correct
7 Correct 1405 ms 592 KB Output is correct
8 Correct 1434 ms 592 KB Output is correct
9 Correct 1438 ms 592 KB Output is correct
10 Correct 1247 ms 604 KB Output is correct
11 Correct 1254 ms 592 KB Output is correct
12 Correct 1259 ms 592 KB Output is correct
13 Correct 1263 ms 592 KB Output is correct
14 Correct 1272 ms 592 KB Output is correct
15 Correct 1214 ms 712 KB Output is correct
16 Correct 1244 ms 592 KB Output is correct
17 Correct 1249 ms 592 KB Output is correct
18 Correct 1314 ms 592 KB Output is correct
19 Execution timed out 9048 ms 1384 KB Time limit exceeded
20 Halted 0 ms 0 KB -