oj.uz

Submission #962610

# Submission time Handle Problem Language Result Execution time Memory
962610 2024-04-14T02:28:45 Z pcc Bubble Sort 2 (JOI18_bubblesort2) C++17
Compilation error
 0 ms 0 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
 
#define pii pair<int,int>
#define fs first
#define sc second
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
 
const int mxn = 5e5+10;
 
const int inf = 1e9+10;
 
vector<int> ans;
 
struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	struct node{
		int mx,smx,tag;
		node(){
			mx = inf;
			smx = 0;
			tag = 0;
		}
	};
	node seg[mxn*4];
	SEG(){
		for(auto &i:seg)i = node();
	}
	void push(int now){
		if(seg[ls].mx >= seg[now].mx)seg[ls].tag += seg[now].tag,seg[ls].mx = seg[now].mx;
		if(seg[rs].mx >= seg[now].mx)seg[rs].tag += seg[now].tag,seg[rs].mx = seg[now].mx;
		seg[now].tag = 0;
		return;
	}
	void pull(int now){
		seg[now].mx = max(seg[ls].mx,seg[rs].mx);
		if(seg[ls].mx<seg[rs].mx)seg[now].smx = max(seg[ls].mx,seg[rs].smx);
		else if(seg[ls].mx>seg[rs].mx)seg[now].smx = max(seg[ls].smx,seg[rs].mx);
		else seg[now].smx = max(seg[ls].smx,seg[rs].smx);
		return;
	}
	void modify(int now,int l,int r,int s,int e,int v){
		if(seg[now].mx<v)return;
		if(l>=s&&e>=r){
			if(seg[now].smx<v){
				seg[now].mx = v;
				seg[now].tag++;
			}
			else{
				push(now);
				modify(ls,l,mid,s,e,v);
				modify(rs,mid+1,r,s,e,v);
				pull(now);
			}
			return;
		}
		push(now);
		if(mid>=s)modify(ls,l,mid,s,e,v);
		if(mid<e)modify(rs,mid+1,r,s,e,v);
		pull(now);
	}
	void dfs(int now,int l,int r){
		if(l == r){
			ans.push_back(seg[now].tag);
			return;
		}
		push(now);
		dfs(ls,l,mid);
		dfs(rs,mid+1,r);
		pull(now);
		return;
	}
#undef ls
#undef rs
#undef mid
};
 
SEG seg;
vector<pii> op[mxn];
int N,Q;
 
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;
}
 
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	N = A.size(),Q = X.size();
 
    ordered_set st;
	for(int i = 0;i<Q;i++){
		int p = X[i],v = V[i];
		ans.push_back(0);
		st.clear();
		for(int j = 0;j<N;j++){
		    ans.back() = max(ans.back(),st.size()-st.order_of_key(pii(A[j],j)));
		    st.insert(pii(A[j],j));
		}
		/*
		int tans = 0,sm = inf;
		for(int j = N-1;j>=0;j--){
			tans += (sm>=A[j]);
			sm = min(sm,A[j]);
		}
		ans.push_back(N-tans);
 
	   */
	}
	return ans;
 
	for(int i = 0;i<N;i++)op[i].push_back(pii(0,A[i]));
	for(int i = 0;i<Q;i++){
		int p = X[i],v = V[i];
		op[p].push_back(pii(i+1,v));
	}
	for(int i = N-1;i>=0;i--){
		int pre = Q;
		while(!op[i].empty()){
			auto [t,v] = op[i].back();op[i].pop_back();
			seg.modify(0,0,Q,t,pre,v);
			pre = t-1;
		}
	}
	seg.dfs(0,0,Q);
	ans.erase(ans.begin());
	for(auto &i:ans)i = N-i;
	return ans;
}

Compilation message

bubblesort2.cpp: In function 'void bubble(std::vector<int>&)':
bubblesort2.cpp:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i = 0;i+1<v.size();i++){
      |                ~~~^~~~~~~~~
bubblesort2.cpp: In function 'bool sorted(std::vector<int>&)':
bubblesort2.cpp:94:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(int i = 0;i+1<v.size();i++){
      |                ~~~^~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:109:73: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, __gnu_pbds::detail::bin_search_tree_set<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::detail::tree_traits<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type)'
  109 |       ans.back() = max(ans.back(),st.size()-st.order_of_key(pii(A[j],j)));
      |                                                                         ^
In file included from /usr/include/c++/10/vector:60,
                 from bubblesort2.h:1,
                 from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:109:73: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_pbds::detail::bin_search_tree_set<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::detail::tree_traits<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'})
  109 |       ans.back() = max(ans.back(),st.size()-st.order_of_key(pii(A[j],j)));
      |                                                                         ^
In file included from /usr/include/c++/10/vector:60,
                 from bubblesort2.h:1,
                 from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:109:73: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_pbds::detail::bin_search_tree_set<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::detail::tree_traits<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'})
  109 |       ans.back() = max(ans.back(),st.size()-st.order_of_key(pii(A[j],j)));
      |                                                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bubblesort2.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:109:73: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  109 |       ans.back() = max(ans.back(),st.size()-st.order_of_key(pii(A[j],j)));
      |                                                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bubblesort2.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:109:73: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  109 |       ans.back() = max(ans.back(),st.size()-st.order_of_key(pii(A[j],j)));
      |                                                                         ^
bubblesort2.cpp:105:7: warning: unused variable 'p' [-Wunused-variable]
  105 |   int p = X[i],v = V[i];
      |       ^
bubblesort2.cpp:105:16: warning: unused variable 'v' [-Wunused-variable]
  105 |   int p = X[i],v = V[i];
      |                ^