oj.uz

답안 #242679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242679 2020-06-28T23:53:07 Z Nightlight Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 48 ms 49144 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
#define L(n) (n << 1)
#define R(n) (n << 1 | 1)
using namespace std;

int N, Q;
vector<int> ans, tmp;
map<int, int> id;
set<int, greater<int>> con[1000005];
int tree[4000005];
int lazy[4000005];

void unlazy(int n, int l, int r) {
	tree[n] += lazy[n];
	if(l != r) {
		lazy[L(n)] += lazy[n];
		lazy[R(n)] += lazy[n];
	}
	lazy[n] = 0;
}

void tt(int n, int l, int r) {
	unlazy(n, l, r);
	if(l == r) {
		cout << tree[n] << " ";
		return;
	}
	int mid = (l + r) >> 1;
	tt(L(n), l, mid);
	tt(R(n), mid + 1, r);
}

void update(int n, int l, int r, int ql, int qr, int val) {
//	if(n == 1) cout << "up: "<< ql << " " << qr << " " << val << "\n";
	unlazy(n, l, r);
	if(qr < l || r < ql) return;
	if(ql <= l && r <= qr) {
		tree[n] += val;
		if(l != r) {
			lazy[L(n)] += val;
			lazy[R(n)] += val;
		}
		return;
	}
	int mid = (l + r) >> 1;
	update(L(n), l, mid, ql, qr, val);
	update(R(n), mid + 1, r, ql, qr, val);
	tree[n] = max(tree[L(n)], tree[R(n)]);
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	N = A.size(), Q = X.size();
	ans.resize(Q);
	tmp = A;
	for(int now : V) tmp.push_back(now);
	sort(tmp.begin(), tmp.end());
	tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
	for(int i = 0; i < tmp.size(); i++) {
		id[tmp[i]] = i;
//		cout << tmp[i] << " ";
	}
//	cout << "\n";
	
	int mac = tmp.size() - 1, val, pos;
	for(int i = 0; i < N; i++) {
		val = id[tmp[i]];
		update(1, 0, mac, val, mac, -1);
		if(con[val].empty()) {
			update(1, 0, mac, val, val, i + 1);
		}else update(1, 0, mac, val, val, i - *con[val].begin());
		con[val].insert(i);
	}
//	tt(1, 0, mac);
//	cout << "\n\n";
	for(int i = 0; i < Q; i++) {
		pos = X[i], val = id[A[pos]];
		if(con[val].size() == 1) update(1, 0, mac, val, val, -pos - 1), con[val].erase(pos);
		else if(*con[val].begin() == pos) {
			con[val].erase(pos);
			update(1, 0, mac, val, val, *con[val].begin() - pos);
		}else con[val].erase(pos);
		update(1, 0, mac, val, mac, 1);
//		tt(1, 0, mac);
//		cout << "\n";

		A[pos] = V[i];
		val = id[A[pos]];
//		cout << val << " " << A[pos] << "\n";
		if(con[val].empty()) update(1, 0, mac, val, val, pos + 1);
		else if(*con[val].begin() < pos) {
			update(1, 0, mac, val, val, pos - *con[val].begin());
		}
		con[val].insert(pos);
		update(1, 0, mac, val, mac, -1);
//		tt(1, 0, mac);
//		cout << "\n\n";
		ans[i] = tree[1];
	}
	return ans;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tmp.size(); i++) {
                 ~~^~~~~~~~~~~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 47488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 47488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 49144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 47488 KB Output isn't correct
2 Halted 0 ms 0 KB -