oj.uz

Submission #737466

# Submission time Handle Problem Language Result Execution time Memory
737466 2023-05-07T08:17:42 Z GrindMachine Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 596 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
	a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
	a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

#include "bubblesort2.h"

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<int> countScans(vector<int> a, vector<int> qx, vector<int> qv) {
	int n = sz(a);
	int q = sz(qx);
	vector<int> ans(q);

	rep(id, q) {
		int x = qx[id];
		int v = qv[id];
		a[x] = v;

		int mx = 0;

		rep(i, n) {
			int inv = 0;
			rep(j, i) {
				inv += (a[j] > a[i]);
			}

			amax(mx, inv);
		}

		ans[id] = mx;
	}

	return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 212 KB Output is correct
2 Correct 187 ms 340 KB Output is correct
3 Correct 2665 ms 384 KB Output is correct
4 Correct 2595 ms 384 KB Output is correct
5 Correct 2622 ms 388 KB Output is correct
6 Correct 2647 ms 384 KB Output is correct
7 Correct 2630 ms 384 KB Output is correct
8 Correct 2608 ms 376 KB Output is correct
9 Correct 2608 ms 380 KB Output is correct
10 Correct 2591 ms 372 KB Output is correct
11 Correct 2712 ms 380 KB Output is correct
12 Correct 3044 ms 368 KB Output is correct
13 Correct 2762 ms 380 KB Output is correct
14 Correct 2854 ms 376 KB Output is correct
15 Correct 2748 ms 372 KB Output is correct
16 Correct 2710 ms 376 KB Output is correct
17 Correct 2719 ms 372 KB Output is correct
18 Correct 2673 ms 376 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 212 KB Output is correct
2 Correct 187 ms 340 KB Output is correct
3 Correct 2665 ms 384 KB Output is correct
4 Correct 2595 ms 384 KB Output is correct
5 Correct 2622 ms 388 KB Output is correct
6 Correct 2647 ms 384 KB Output is correct
7 Correct 2630 ms 384 KB Output is correct
8 Correct 2608 ms 376 KB Output is correct
9 Correct 2608 ms 380 KB Output is correct
10 Correct 2591 ms 372 KB Output is correct
11 Correct 2712 ms 380 KB Output is correct
12 Correct 3044 ms 368 KB Output is correct
13 Correct 2762 ms 380 KB Output is correct
14 Correct 2854 ms 376 KB Output is correct
15 Correct 2748 ms 372 KB Output is correct
16 Correct 2710 ms 376 KB Output is correct
17 Correct 2719 ms 372 KB Output is correct
18 Correct 2673 ms 376 KB Output is correct
19 Execution timed out 9081 ms 596 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 9078 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 212 KB Output is correct
2 Correct 187 ms 340 KB Output is correct
3 Correct 2665 ms 384 KB Output is correct
4 Correct 2595 ms 384 KB Output is correct
5 Correct 2622 ms 388 KB Output is correct
6 Correct 2647 ms 384 KB Output is correct
7 Correct 2630 ms 384 KB Output is correct
8 Correct 2608 ms 376 KB Output is correct
9 Correct 2608 ms 380 KB Output is correct
10 Correct 2591 ms 372 KB Output is correct
11 Correct 2712 ms 380 KB Output is correct
12 Correct 3044 ms 368 KB Output is correct
13 Correct 2762 ms 380 KB Output is correct
14 Correct 2854 ms 376 KB Output is correct
15 Correct 2748 ms 372 KB Output is correct
16 Correct 2710 ms 376 KB Output is correct
17 Correct 2719 ms 372 KB Output is correct
18 Correct 2673 ms 376 KB Output is correct
19 Execution timed out 9081 ms 596 KB Time limit exceeded
20 Halted 0 ms 0 KB -