제출 #102100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102100		gs14004	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3153 ms	67400 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
const int MAXN = 500005;

pi a[MAXN];
int p[2 * MAXN];
int chk[2 * MAXN];

struct seg{
	int tree[2100000], lazy[2100000];
	void init(){
		fill(tree, tree + 2100000, -1e9);
	}
	void lazydown(int p){
		lazy[2*p] += lazy[p];
		lazy[2*p+1] += lazy[p];
		tree[2*p] += lazy[p];
		tree[2*p+1] += lazy[p];
		lazy[p] = 0;
	}
	void add(int s, int e, int ps, int pe, int p, int v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			tree[p] += v;
			lazy[p] += v;
			return;
		}
		int pm = (ps+pe)/2;
		lazydown(p);
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm+1, pe, 2*p+1, v);
		tree[p] = max(tree[2*p], tree[2*p+1]);
	}
	void upd(int pos, int s, int e, int p, int v){
		if(s == e){
			tree[p] = v;
			return;
		}
		int m = (s+e)/2;
		lazydown(p);
		if(pos <= m) upd(pos, s, m, 2*p, v);
		else upd(pos, m+1, e, 2*p+1, v);
		tree[p] = max(tree[2*p], tree[2*p+1]);
	}
	int query(int pos, int s, int e, int p){
		if(s == e) return tree[p];
		int m = (s+e)/2;
		lazydown(p);
		if(pos <= m) return query(pos, s, m, 2*p);
		else return query(pos, m+1, e, 2*p+1);
	}
}seg;

struct bit{
	int tree[2 * MAXN];
	void add(int x, int v){
		while(x < 2 * MAXN){
			tree[x] += v;
			x += x & -x;
		}
	}
	int query(int x){
		int ret = 0;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret;
	}
}bit;

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int n=A.size();
	int Q=X.size();
	std::vector<int> answer(Q);	
	for(int i=0; i<n; i++) a[i] = pi(A[i], i);
	vector<pi> v;
	for(int i=0; i<n; i++) v.push_back(a[i]);
	for(int i=0; i<Q; i++) v.push_back(pi(V[i], X[i]));
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	auto getpos = [&](pi x){
		return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
	};
	seg.init();
	for(int i=0; i<n; i++){
		int pos = getpos(a[i]);
		p[pos] = i;
		chk[pos] = 1;
		bit.add(pos, 1);
	}
	for(int i=1; i<=v.size(); i++){
		if(chk[i]) p[i] -= bit.query(i) - 1;
		else p[i] = -1e9;
		seg.upd(i, 1, v.size(), 1, p[i]);
	}
	for(int i=0; i<Q; i++){
		int curpos = getpos(a[X[i]]);
		a[X[i]].first = V[i];
		int nxtpos = getpos(a[X[i]]);
		if(curpos <= nxtpos){
			int val = seg.query(curpos, 1, v.size(), 1) + bit.query(curpos) - 1;
			bit.add(curpos, -1);
			seg.add(curpos + 1, nxtpos, 1, v.size(), 1, 1);
			bit.add(nxtpos, 1);
			seg.upd(curpos, 1, v.size(), 1, -1e9);
			seg.upd(nxtpos, 1, v.size(), 1, val - bit.query(nxtpos) + 1);
		}
		else{
			int val = seg.query(curpos, 1, v.size(), 1) + bit.query(curpos) - 1;
			bit.add(curpos, -1);
			seg.add(nxtpos + 1, curpos, 1, v.size(), 1, -1);
			bit.add(nxtpos, 1);
			seg.upd(curpos, 1, v.size(), 1, -1e9);
			seg.upd(nxtpos, 1, v.size(), 1, val - bit.query(nxtpos) + 1);
		}
		int ans = max(seg.tree[1], 0);
		answer[i] = ans;
	}
	return answer;
}

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

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

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40