oj.uz

Submission #102442

# Submission time Handle Problem Language Result Execution time Memory
102442 2019-03-25T02:53:11 Z IOrtroiii Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 829 ms 972 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 500500;
const int MAGIC = 1616;

struct SegmentTree {
	vector<int> lz;
	vector<int> cnt;
	vector<int> val;
	void resize(int n) {
		lz.resize((n << 2) + 5);
		cnt.resize((n << 2) + 5);
		val.resize((n << 2) + 5);
	}
	void pull(int v) {
		cnt[v] = cnt[v << 1] + cnt[v << 1 | 1];
		val[v] = max(val[v << 1], val[v << 1 | 1]);
	}
	void push(int v,int l,int r) {
		if (lz[v]) {
			val[v] += lz[v];
			if (l < r) {
				lz[v << 1] += lz[v];
				lz[v << 1 | 1] += lz[v];
			}
			lz[v] = 0;
		}
	}
	void addVal(int v,int l,int r,int L,int R) {
		
	}
};

vector<int> countScans(vector<int> a,vector<int> x,vector<int> y) {
	// brute
	int n = a.size(), q = x.size();
	vector<int> f(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			f[i] += a[j] > a[i];
		} 
	}
	vector<int> ans;
	for (int i = 0; i < q; ++i) {
		// delval
		for (int j = x[i] + 1; j < n; ++j) {
			if (a[j] < a[x[i]]) {
				f[j]--;
			}
		}	
		a[x[i]] = y[i];
		for (int j = x[i] + 1; j < n; ++j) {
			if (a[j] < a[x[i]]) {
				f[j]++;
			}
		}
		f[x[i]] = 0;
		for (int j = 0; j < n; ++j) {
			if (a[j] > a[x[i]]) {
				f[x[i]]++;
			}
		}
		ans.push_back(*max_element(f.begin(), f.end()));
	}
	return ans;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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