Submission #539273

#	Time	Username	Problem	Language	Result	Execution time	Memory
539273		NaimSS	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2341 ms	51560 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define ff first
#define ss second
const int MAXN = 1e6 + 100;
int tree[4*MAXN];
int lazy[4*MAXN];
int n;

const int inf = 1e9;

void propagate(int no,int i,int j){
	if(lazy[no]==0)return;
	tree[no]+=lazy[no];
	if(i!=j){
		lazy[2*no]+=lazy[no];
		lazy[2*no+1]+=lazy[no];
	}
	lazy[no] = 0;
}

void update(int no,int i,int j,int a,int b,int v){
	if(a > b)return;
	propagate(no,i,j);
	if(i>b || j<a || i>j)return;
	if(a<=i && j<=b){
		tree[no] += v;
		if(i!=j){
			lazy[2*no]+=v;
			lazy[2*no+1]+=v;
		}
		return;
	}
	int m = (i+j)/2;
	int l = 2*no,r=2*no+1;
	update(l,i,m,a,b,v);
	update(r,m+1,j,a,b,v);	
	tree[no] = max(tree[l],tree[r]);
}

int query(int no,int i,int j,int a,int b){
	if(i>b || j<a || i>j)return -inf;
	
	propagate(no,i,j);
	
	if(a<=i && j<=b)return tree[no];
	
	int m = (i+j)/2;
	int l = 2*no,r=2*no+1;
	
	return max(query(l,i,m,a,b),query(r,m+1,j,a,b));
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int Q=X.size();
	std::vector<int> answer(Q);
	vector<pii> vec;
	int n = A.size();
	for(int i=0;i<n;i++){
		vec.push_back(pii(A[i],i));
	}
	for(int i=0;i<Q;i++){
		vec.push_back(pii(V[i],X[i]));
	}
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	int tam = vec.size();
	auto Pos = [&](int id){
		return (lower_bound(vec.begin(),vec.end(),pii(A[id],id)) - vec.begin()) + 1;
	};
	for(int i=0;i<n;i++){
		int pos = Pos(i);
		update(1,1,tam,pos,pos,i);
		update(1,1,tam,pos+1,tam,-1);
	}
	for (int j=0;j<Q;j++) {
		int pos = Pos(X[j]);
		update(1,1,tam,pos,pos,-X[j]);
		update(1,1,tam,pos+1,tam,+1);
		A[X[j]] = V[j];
		pos = Pos(X[j]);
		update(1,1,tam,pos,pos,+X[j]);
		update(1,1,tam,pos+1,tam,-1);
		answer[j] = query(1,1,tam,1,tam);
	}
	return answer;
}

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