제출 #242680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242680		Nightlight	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	4915 ms	166960 KiB

bubblesort2

#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[A[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);
	}
//	cout << tree[1] << "\n";
//	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;
}

컴파일 시 표준 에러 (stderr) 메시지

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: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40