oj.uz

Submission #962616

# Submission time Handle Problem Language Result Execution time Memory
962616 2024-04-14T03:11:59 Z pcc Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 37612 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt,avx2,sse4")
using namespace std;
using namespace __gnu_pbds;

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

template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

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<pii> st;

	for(int i = 0;i<Q;i++){
		int p = X[i],v = V[i];
		A[p] = v;

		int tans = 0;
		st.clear();
		for(int j = 0;j<N;j++){
			tans = max(tans,(int)st.size()-(int)st.order_of_key(pii(A[j],j)));
			st.insert(pii(A[j],j));
		}
		ans.push_back(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:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i = 0;i+1<v.size();i++){
      |                ~~~^~~~~~~~~
bubblesort2.cpp: In function 'bool sorted(std::vector<int>&)':
bubblesort2.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for(int i = 0;i+1<v.size();i++){
      |                ~~~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 35672 KB Output is correct
2 Correct 158 ms 35720 KB Output is correct
3 Correct 828 ms 35812 KB Output is correct
4 Correct 921 ms 36064 KB Output is correct
5 Correct 853 ms 35820 KB Output is correct
6 Correct 841 ms 35812 KB Output is correct
7 Correct 822 ms 35820 KB Output is correct
8 Correct 827 ms 35820 KB Output is correct
9 Correct 824 ms 35812 KB Output is correct
10 Correct 726 ms 35840 KB Output is correct
11 Correct 711 ms 35832 KB Output is correct
12 Correct 713 ms 35820 KB Output is correct
13 Correct 706 ms 35824 KB Output is correct
14 Correct 765 ms 35824 KB Output is correct
15 Correct 698 ms 35828 KB Output is correct
16 Correct 708 ms 35672 KB Output is correct
17 Correct 716 ms 35924 KB Output is correct
18 Correct 757 ms 35820 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 35672 KB Output is correct
2 Correct 158 ms 35720 KB Output is correct
3 Correct 828 ms 35812 KB Output is correct
4 Correct 921 ms 36064 KB Output is correct
5 Correct 853 ms 35820 KB Output is correct
6 Correct 841 ms 35812 KB Output is correct
7 Correct 822 ms 35820 KB Output is correct
8 Correct 827 ms 35820 KB Output is correct
9 Correct 824 ms 35812 KB Output is correct
10 Correct 726 ms 35840 KB Output is correct
11 Correct 711 ms 35832 KB Output is correct
12 Correct 713 ms 35820 KB Output is correct
13 Correct 706 ms 35824 KB Output is correct
14 Correct 765 ms 35824 KB Output is correct
15 Correct 698 ms 35828 KB Output is correct
16 Correct 708 ms 35672 KB Output is correct
17 Correct 716 ms 35924 KB Output is correct
18 Correct 757 ms 35820 KB Output is correct
19 Execution timed out 9099 ms 36276 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9052 ms 37612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 35672 KB Output is correct
2 Correct 158 ms 35720 KB Output is correct
3 Correct 828 ms 35812 KB Output is correct
4 Correct 921 ms 36064 KB Output is correct
5 Correct 853 ms 35820 KB Output is correct
6 Correct 841 ms 35812 KB Output is correct
7 Correct 822 ms 35820 KB Output is correct
8 Correct 827 ms 35820 KB Output is correct
9 Correct 824 ms 35812 KB Output is correct
10 Correct 726 ms 35840 KB Output is correct
11 Correct 711 ms 35832 KB Output is correct
12 Correct 713 ms 35820 KB Output is correct
13 Correct 706 ms 35824 KB Output is correct
14 Correct 765 ms 35824 KB Output is correct
15 Correct 698 ms 35828 KB Output is correct
16 Correct 708 ms 35672 KB Output is correct
17 Correct 716 ms 35924 KB Output is correct
18 Correct 757 ms 35820 KB Output is correct
19 Execution timed out 9099 ms 36276 KB Time limit exceeded
20 Halted 0 ms 0 KB -