oj.uz

Submission #160481

# Submission time Handle Problem Language Result Execution time Memory
160481 2019-10-27T15:51:14 Z iefnah06 Bubble Sort 2 (JOI18_bubblesort2) C++11
0 / 100
 73 ms 64888 KB 
#include "bubblesort2.h"

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int INF = 1e9;

const int MAXN = 5.1e5;
const int MAXQ = 5.1e5;
const int MAXS = MAXN + MAXQ;
int N, Q;

struct seg {
	seg* ch[2];
	ll maxval;
	ll lazyval;

	seg() {
		maxval = lazyval = 0;
	}

	void increment(ll a) {
		maxval += a;
		lazyval += a;
	}

	void update() {
		assert(ch[0] && ch[1]);
		maxval = lazyval + max(ch[0]->maxval, ch[1]->maxval);
	}
};
seg nodes[MAXS*2];
int NODE = 0;
seg* ROOT;

pair<int, int> pairs[MAXS];
int S;

seg* build(int x = 0, int y = S) {
	seg* n = &nodes[NODE++];
	if (y - x > 1) {
		int z = (x + y) / 2;
		n->ch[0] = build(x, z);
		n->ch[1] = build(z, y);
		n->update();
	}
	return n;
}

void update(int l, int r, int v, int x, int y, seg* n) {
	if (l <= x && y <= r) {
		n->increment(v);
	} else {
		int z = (x + y) / 2;
		if (l < z) {
			update(l, r, v, x, z, n->ch[0]);
		}
		if (z < r) {
			update(l, r, v, z, y, n->ch[1]);
		}
		n->update();
	}
}

void update(int l, int r, int v) {
	if (l < r) {
		update(l, r, v, 0, S, ROOT);
	}
}

ll query() {
	return ROOT->maxval;
}

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

	for (int i = 0; i < N; i++) {
		pairs[i] = {A[i], i};
	}
	for (int i = 0; i < Q; i++) {
		pairs[i+N] = {V[i], X[i]};
	}
	S = N + Q;
	sort(pairs, pairs + S);
	S = int(unique(pairs, pairs + S) - pairs);

	auto modify = [&](int v, int i, int k) -> void {
		int j = int(lower_bound(pairs, pairs + S, pair<int, int>(v, i)) - pairs);
		assert(make_pair(v, i) == pairs[j]);
		update(j, j+1, k * (INF + i));
		update(j+1, S, k * -1);
	};

	ROOT = build();
	update(0, S, -INF);
	for (int i = 0; i < N; i++) {
		modify(A[i], i, 1);
	}

	vector<int> answer(Q);
	for (int q = 0; q < Q; q++) {
		update(A[X[q]], X[q], -1);
		update(V[q], X[q], 1);
		A[X[q]] = V[q];
		answer[q] = query();
	}
	return answer;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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