Submission #1013533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013533		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2735 ms	162052 KiB

bubblesort2

// #include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using pii=pair<int,int>;

#define pb push_back
#define all(v) v.begin(),v.end()
vector<int> a;
int n;
struct Node{
	int val=0;
	int lazy=0;
	Node* left,*right;
	Node() : left(nullptr),right(nullptr) {}
};
Node* root;
void build(Node* node,int l,int r){
	if(l==r) return;
	int mid=(l+r)/2;
	node->left=new Node();
	node->right=new Node();
	build(node->left,l,mid);
	build(node->right,mid+1,r);
}
void push(Node* node,int l,int r){
	if(node->lazy==0) return;
	node->val+=node->lazy;
	if(node->left) {
		node->left->lazy+=node->lazy;
	}
	if(node->right) {
		node->right->lazy+=node->lazy;
	}
	node->lazy=0;
}
void update(Node* node,int l,int r,int ql,int qr,int x){
	push(node,l,r);
	if(ql>r||qr<l) return;
	if(ql<=l&&r<=qr){
		node->lazy+=x;
		push(node,l,r);
		return;
	}
	int mid=(l+r)/2;
	update(node->left,l,mid,ql,qr,x);
	update(node->right,mid+1,r,ql,qr,x);
	push(node,l,r);
	node->val=max(node->left->val,node->right->val);
}

vector<int> countScans(vector<int> A,vector<int> x,vector<int> y){
	a=A;
	root=new Node();
	n=a.size();
	int q=x.size();
	build(root,0,n+q);
	vector<pii> v;
	for(int i=0;i<n;i++){
		v.pb({a[i],i});
	}
	for(int i=0;i<q;i++){
		v.pb({y[i],x[i]});
	}
	sort(all(v));
	map<pii,int> mp;
	for(int i=0;i<n+q;i++){
		mp[v[i]]=i;
	}
	for(int i=0;i<n;i++){
		a[i]=mp[{a[i],i}];
	}
	for(int i=0;i<q;i++){
		y[i]=mp[{y[i],x[i]}];
	}
	vector<int> Ans(q);
	int sz=n+q;
	auto ch  = [&](int i,int x){
		update(root,0,sz,a[i],a[i],i*x);
		update(root,0,sz,a[i]+1,sz,-x);
	};
	for(int i=0;i<n;i++){
		ch(i,1);
	}
	for(int i=0;i<q;i++){
		ch(x[i],-1);
		a[x[i]]=y[i];
		ch(x[i],1);
		Ans[i]=root->val;
	}
	
	return Ans;
}



#ifdef IOI
// #include "bubblesort2.h"

// #include <cstdio>
// #include <cstdlib>
// #include <vector>

int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}

int main(){
	int N,Q;
	N=readInt();
	Q=readInt();
	
	vector<int> A(N);
	for(int i=0;i<N;i++)
		A[i]=readInt();
	
	vector<int> X(Q),V(Q);
	for(int j=0;j<Q;j++){
		X[j]=readInt();
		V[j]=readInt();
	}
	
	vector<int> res=countScans(A,X,V);
	
	for(int j=0;j<int(res.size());j++)
		printf("%d\n",res[j]);
}

#endif

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