oj.uz

Submission #164038

# Submission time Handle Problem Language Result Execution time Memory
164038 2019-11-17T06:30:10 Z dolphingarlic Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 316 ms 167672 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define FOR(i, x, y) for (int i = x; i < y; i++)
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> indexed_set;

indexed_set segtree[2000000];
int N;
vector<int> A;

void build(int node = 1, int l = 0, int r = N - 1) {
	if (l == r) segtree[node].insert(A[l]);
	else {
		int mid = (l + r) / 2;
		build(node * 2, l, mid);
		build(node * 2 + 1, mid + 1, r);

		for (int i : segtree[node * 2]) segtree[node].insert(i);
		for (int i : segtree[node * 2 + 1]) segtree[node].insert(i);
	}
}
int query(int a, int b, int val, int node = 1, int l = 0, int r = N - 1) {
	if (a > r || b < l) return 0;
	if (a <= l && b >= r) return segtree[node].order_of_key(val);

	int mid = (l + r) / 2;
	return query(a, b, val, node * 2, l, mid) + query(a, b, val, node * 2 + 1, mid + 1, r);
}
void update(int pos, int old, int val, int node = 1, int l = 0, int r = N - 1) {
	segtree[node].erase(segtree[node].find(old));
	segtree[node].insert(val);
	if (l != r) {
		int mid = (l + r) / 2;
		if (pos > mid) update(pos, old, val, node * 2 + 1, mid + 1, r);
		else update(pos, old, val, node * 2, l, mid);
	}
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
    int Q = X.size();
	N = A.size();
	::A = A;
    vector<int> answer(Q);

	build();
	int curr = 0;
	FOR(i, 0, N) curr += query(i, N - 1, A[i]);

    FOR(i, 0, Q) {
		curr -= query(X[i], N - 1, A[X[i]]) - query(0, X[i], A[X[i]]);
		update(X[i], A[X[i]], V[i]);
		A[X[i]] = V[i];
		curr += query(X[i], N - 1, A[X[i]]) - query(0, X[i], A[X[i]]);
		answer[i] = curr;
    }

    return answer;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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