oj.uz

답안 #962599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962599 2024-04-14T02:06:26 Z pcc Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 75 ms 35904 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;

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

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 35776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 35776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 35904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 35776 KB Output isn't correct
2 Halted 0 ms 0 KB -