제출 #1282379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282379		PlayVoltz	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	3125 ms	116288 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

struct node{
	int s, e, m, val, lazy;
	node *l, *r;
	void create(){
		if (l==nullptr){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void propagate(){
		val+=lazy;
		if (s!=e){
			create();
			l->lazy+=lazy;
			r->lazy+=lazy;
		}
		lazy=0;
	}
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val=lazy=0;
		l=r=nullptr;
	}
	void up(int left, int right, int v){
		if (left>right)return;
		propagate();
		if (s==left && e==right)lazy+=v;
		else{
			create();
			if (right<=m)l->up(left, right, v);
			else if (left>m)r->up(left, right, v);
			else l->up(left, m, v), r->up(m+1, right, v);
			r->propagate(), l->propagate();
			val=max(l->val, r->val);
		}
		
	}
	int query(int left, int right){
		propagate();
		if (s==left && e==right)return val;
		create();
		if (right<=m)return l->query(left, right);
		else if (left>m)return r->query(left, right);
		else return max(l->query(left, m), r->query(m+1, right));
	}
}*st;

vector<int> countScans(vector<int> vect, vector<int> id, vector<int> v){
	int n=vect.size(), q=v.size();
	vector<pii> ord;
	for (int i=0; i<n; ++i)ord.pb(mp(vect[i], i));
	for (int i=0; i<q; ++i)ord.pb(mp(v[i], id[i]));
	sort(ord.begin(), ord.end());
	ord.erase(unique(ord.begin(), ord.end()), ord.end());
	st = new node(0, ord.size()-1);
	for (int i=0; i<n; ++i){
		int p=lower_bound(ord.begin(), ord.end(), mp(vect[i], i))-ord.begin();
		st->up(p, p, i);
		st->up(p+1, ord.size()-1, -1);
	}
	vector<int> ans(q);
	for (int i=0; i<q; ++i){
		int p=lower_bound(ord.begin(), ord.end(), mp(vect[id[i]], id[i]))-ord.begin();
		st->up(p, p, -id[i]);
		st->up(p+1, ord.size()-1, 1);
		vect[id[i]]=v[i];
		p=lower_bound(ord.begin(), ord.end(), mp(vect[id[i]], id[i]))-ord.begin();
		st->up(p, p, id[i]);
		st->up(p+1, ord.size()-1, -1);
		ans[i]=st->query(0, ord.size()-1);
	}
	return ans;
}

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