제출 #962641

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

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt,avx2,sse4")
using namespace std;

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fs first
#define sc second

const int mxn = 5e5+10;
const ll inf = 1e9+10;



namespace BRUTE{

	void bubble(vector<int> &v){
		for(int i = 0;i+1<v.size();i++){
			if(v[i]>v[i+1])swap(v[i],v[i+1]);
		}
		return;
	}
	bool sorted(vector<int> &v){
		for(int i = 0;i+1<v.size();i++){
			if(v[i]>v[i+1])return false;
		}
		return true;
	}

	int getans(vector<int> &A){
		int re = 0;
		auto tmp = A;
		while(!sorted(tmp))re++,bubble(tmp);
		return re;
	}

}

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	pll seg[mxn*8];
	SEG(){}
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now].sc += v;
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,v);
		if(mid<e)modify(rs,mid+1,r,s,e,v);
		seg[now].fs = max(seg[ls].fs+seg[ls].sc,seg[rs].fs+seg[rs].sc);
	}
	int getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now].fs+seg[now].sc;
		if(mid>=e)return seg[now].sc+getval(ls,l,mid,s,e);
		else if(mid<s)return seg[now].sc+getval(rs,mid+1,r,s,e);
		else return max(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e))+seg[now].sc;
	}
#undef ls
#undef rs
#undef mid
};

ll arr[mxn];
pll req[mxn];
int N,Q;
vector<ll> all;
SEG seg;
vector<int> ans;

void del(int p){
	seg.modify(0,0,all.size(),arr[p],arr[p],-p-inf);
	seg.modify(0,0,all.size(),arr[p]+1,all.size(),1);
	return;
}
void add(int p){
	seg.modify(0,0,all.size(),arr[p],arr[p],inf);
	seg.modify(0,0,all.size(),arr[p],arr[p],p);
	seg.modify(0,0,all.size(),arr[p]+1,all.size(),-1);
	return;
}

#define _all(T) T.begin(),T.end()
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	all.push_back(inf*inf);
	all.push_back(0);
	N = A.size(),Q = X.size();
	for(int i = 0;i<N;i++)arr[i] = 1ll*A[i]*mxn+i,all.push_back(arr[i]);
	for(int i = 0;i<Q;i++){
		req[i].fs = X[i];
		req[i].sc = 1ll*V[i]*mxn+req[i].fs;
		all.push_back(req[i].sc);
	}
	sort(all.begin(),all.end());all.resize(unique(all.begin(),all.end())-all.begin());
	for(int i = 0;i<N;i++)arr[i] = lower_bound(_all(all),arr[i])-all.begin();
	for(int i = 0;i<Q;i++)req[i].sc = lower_bound(_all(all),req[i].sc)-all.begin();
	seg.modify(0,0,all.size(),0,all.size(),-inf);
	for(int i = 0;i<N;i++){
		seg.modify(0,0,all.size(),arr[i],arr[i],inf);
		seg.modify(0,0,all.size(),arr[i],arr[i],i);
		seg.modify(0,0,all.size(),arr[i]+1,all.size(),-1);
	}
	for(int i = 0;i<Q;i++){
		del(req[i].fs);
		arr[req[i].fs] = req[i].sc;
		add(req[i].fs);
		ans.push_back(seg.getval(0,0,all.size(),0,all.size()));
	}
	return ans;
}

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

bubblesort2.cpp: In function 'void BRUTE::bubble(std::vector<int>&)':
bubblesort2.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i = 0;i+1<v.size();i++){
      |                 ~~~^~~~~~~~~
bubblesort2.cpp: In function 'bool BRUTE::sorted(std::vector<int>&)':
bubblesort2.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int i = 0;i+1<v.size();i++){
      |                 ~~~^~~~~~~~~

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