제출 #125586

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

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct SEG{
	SEG(int l, int r, int mx, int lazy, int sum) : l(l), r(r), mx(mx), lazy(lazy), sum(sum) {}
	int l, r;
	int mx, lazy;
	int sum;
};
vector<SEG> seg;

void init(int idx, int s, int e){
	if(s==e)	return;
	seg[idx].l = seg.size(); seg.pb({-1, -1, -INF, 0, 0});
	seg[idx].r = seg.size(); seg.pb({-1, -1, -INF, 0, 0});
	init(seg[idx].l, s, (s+e)/2); init(seg[idx].r, (s+e)/2+1, e);
}


void update(int idx, int s, int e, int x, int y){
	if(seg[idx].lazy!=0){
		if(seg[idx].l!=-1){
			seg[seg[idx].l].lazy += seg[idx].lazy; seg[seg[idx].l].mx += seg[idx].lazy;
			seg[seg[idx].r].lazy += seg[idx].lazy; seg[seg[idx].r].mx += seg[idx].lazy;
		}
		seg[idx].lazy = 0;
	}
	if(y==-INF){
		seg[idx].sum--;
	}else{
		seg[idx].sum++;
	}
	if(s==e){
		seg[idx].mx = y;
		return;
	}
	if(x<=(s+e)/2){
		update(seg[idx].l, s, (s+e)/2, x, y);
	}else{
		update(seg[idx].r, (s+e)/2+1, e, x, y);
	}
	seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
}

void lazy(int idx, int s, int e, int x, int y, int z){
	if(seg[idx].lazy!=0){
		if(seg[idx].l!=-1){
			seg[seg[idx].l].lazy += seg[idx].lazy; seg[seg[idx].l].mx += seg[idx].lazy;
			seg[seg[idx].r].lazy += seg[idx].lazy; seg[seg[idx].r].mx += seg[idx].lazy;
		}
		seg[idx].lazy = 0;
	}
	if(x<=s && e<=y){
		seg[idx].lazy += z;
		seg[idx].mx += z;
		return;
	}
	if(x>e || y<s)	return;
	lazy(seg[idx].l, s, (s+e)/2, x, y, z);
	lazy(seg[idx].r, (s+e)/2+1, e, x, y, z);
	seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
}

int max(int idx, int s, int e, int x, int y){
	if(seg[idx].lazy!=0){
		if(seg[idx].l!=-1){
			seg[seg[idx].l].lazy += seg[idx].lazy; seg[seg[idx].l].mx += seg[idx].lazy;
			seg[seg[idx].r].lazy += seg[idx].lazy; seg[seg[idx].r].mx += seg[idx].lazy;
		}
		seg[idx].lazy = 0;
	}
	if(x<=s && e<=y){
		return seg[idx].mx;
	}
	if(s>y || e<x)	return -INF;
	return max(max(seg[idx].l, s, (s+e)/2, x, y), max(seg[idx].r, (s+e)/2+1, e, x, y));
}

int sum(int idx, int s, int e, int x, int y){
	if(x<=s && e<=y){
		return seg[idx].sum;
	}else if(x>e || y<s)	return 0;
	return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
}

vector<pii> vt;

map<pii, int> mp;

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	int Q = X.size();
	vector<int> answer(Q);
	for(int i=0; i<A.size(); i++){
		vt.pb({A[i], i});
	}
	for(int i=0; i<Q; i++){
		vt.pb({V[i], X[i]});
	}
	sort(vt.begin(), vt.end());
	vt.erase(unique(vt.begin(), vt.end()), vt.end());
	for(int i=0; i<vt.size(); i++){
		mp[vt[i]] = i;
	}
	seg.pb({-1, -1, -INF, 0, 0});
	init(0, 0, vt.size()-1);
	for(int i=0; i<A.size(); i++){
		int t = mp[{A[i], i}];
		update(0, 0, vt.size()-1, t, i);
	}
	for(int i=0; i<A.size(); i++){
		int t = mp[{A[i], i}];
		lazy(0, 0, vt.size()-1, t+1, vt.size()-1, -1);
	}
	for(int i=0; i<Q; i++){
		int idx = X[i];
		pii prv = {A[idx], idx};
		lazy(0, 0, vt.size()-1, mp[prv]+1, vt.size()-1, 1);
		update(0, 0, vt.size()-1, mp[prv], -INF);
		pii now = {V[i], idx};
		A[idx] = V[i];
		update(0, 0, vt.size()-1, mp[now], idx - sum(0, 0, vt.size()-1, 0, mp[now]-1));
		lazy(0, 0, vt.size()-1, mp[now]+1, vt.size()-1, -1);
		answer[i] = max(0, 0, vt.size()-1, 0, vt.size()-1);
	}
	return answer;
}

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

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<A.size(); i++){
               ~^~~~~~~~~
bubblesort2.cpp:122:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
bubblesort2.cpp:127:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<A.size(); i++){
               ~^~~~~~~~~
bubblesort2.cpp:131:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<A.size(); i++){
               ~^~~~~~~~~

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