oj.uz

Submission #962605

# Submission time Handle Problem Language Result Execution time Memory
962605 2024-04-14T02:12:26 Z pcc Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 35996 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;


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

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();

	for(int i = 0;i<Q;i++){
		int p = X[i],v = V[i];
		A[p] = v;
		ans.push_back(0);
		auto ta = A;
		while(!sorted(ta)){
			ans.back()++;
			bubble(ta);
		}
		/*
		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:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i = 0;i+1<v.size();i++){
      |                ~~~^~~~~~~~~
bubblesort2.cpp: In function 'bool sorted(std::vector<int>&)':
bubblesort2.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0;i+1<v.size();i++){
      |                ~~~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 35664 KB Output is correct
2 Correct 641 ms 35692 KB Output is correct
3 Correct 8643 ms 35768 KB Output is correct
4 Correct 8552 ms 35676 KB Output is correct
5 Correct 3968 ms 35740 KB Output is correct
6 Correct 698 ms 35740 KB Output is correct
7 Correct 1584 ms 35924 KB Output is correct
8 Correct 2344 ms 35672 KB Output is correct
9 Correct 4049 ms 35752 KB Output is correct
10 Correct 6693 ms 35924 KB Output is correct
11 Correct 6780 ms 35744 KB Output is correct
12 Correct 6640 ms 35744 KB Output is correct
13 Correct 6781 ms 35744 KB Output is correct
14 Correct 6722 ms 35748 KB Output is correct
15 Correct 6664 ms 35748 KB Output is correct
16 Correct 6633 ms 35744 KB Output is correct
17 Correct 6776 ms 35736 KB Output is correct
18 Correct 6760 ms 35744 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 35664 KB Output is correct
2 Correct 641 ms 35692 KB Output is correct
3 Correct 8643 ms 35768 KB Output is correct
4 Correct 8552 ms 35676 KB Output is correct
5 Correct 3968 ms 35740 KB Output is correct
6 Correct 698 ms 35740 KB Output is correct
7 Correct 1584 ms 35924 KB Output is correct
8 Correct 2344 ms 35672 KB Output is correct
9 Correct 4049 ms 35752 KB Output is correct
10 Correct 6693 ms 35924 KB Output is correct
11 Correct 6780 ms 35744 KB Output is correct
12 Correct 6640 ms 35744 KB Output is correct
13 Correct 6781 ms 35744 KB Output is correct
14 Correct 6722 ms 35748 KB Output is correct
15 Correct 6664 ms 35748 KB Output is correct
16 Correct 6633 ms 35744 KB Output is correct
17 Correct 6776 ms 35736 KB Output is correct
18 Correct 6760 ms 35744 KB Output is correct
19 Execution timed out 9040 ms 35996 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 9033 ms 35956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 35664 KB Output is correct
2 Correct 641 ms 35692 KB Output is correct
3 Correct 8643 ms 35768 KB Output is correct
4 Correct 8552 ms 35676 KB Output is correct
5 Correct 3968 ms 35740 KB Output is correct
6 Correct 698 ms 35740 KB Output is correct
7 Correct 1584 ms 35924 KB Output is correct
8 Correct 2344 ms 35672 KB Output is correct
9 Correct 4049 ms 35752 KB Output is correct
10 Correct 6693 ms 35924 KB Output is correct
11 Correct 6780 ms 35744 KB Output is correct
12 Correct 6640 ms 35744 KB Output is correct
13 Correct 6781 ms 35744 KB Output is correct
14 Correct 6722 ms 35748 KB Output is correct
15 Correct 6664 ms 35748 KB Output is correct
16 Correct 6633 ms 35744 KB Output is correct
17 Correct 6776 ms 35736 KB Output is correct
18 Correct 6760 ms 35744 KB Output is correct
19 Execution timed out 9040 ms 35996 KB Time limit exceeded
20 Halted 0 ms 0 KB -