Submission #962597

#	Time	Username	Problem	Language	Result	Execution time	Memory
962597		pcc	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	15 ms	36696 KiB

bubblesort2

#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;

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<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;
}

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