| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1257683 | Bahamin | Bubble Sort 2 (JOI18_bubblesort2) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
#define lid id << 1
#define rid id << 1 | 1
#define mid ((r + l) >> 1)
const ll MAX_N = 1e6 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const ll LOG = 30;
set<ll> cnt[MAX_N];
ll ma[MAX_N];
ll n;
ll seg[MAX_N << 2];
ll ops[MAX_N << 2];
void build(ll l, ll r, ll id)
{
if (l == r - 1)
{
seg[id] = ma[l];
return;
}
build(l, mid, lid);
build(mid, r, rid);
seg[id] = max(seg[lid], seg[rid]);
}
void move(ll l, ll r, ll id)
{
if (l == r - 1) return;
seg[lid] += ops[id];
seg[rid] += ops[id];
ops[lid] += ops[id];
ops[rid] += ops[id];
ops[id] = 0;
}
void upd(ll s, ll t, ll x, ll l, ll r, ll id)
{
if (s >= t) return;
move(l, r, id);
if (s <= l && t >= r)
{
seg[id] += x;
ops[id] += x;
return;
}
if (s < mid) upd(s, t, x, l, mid, lid);
else upd(s, t, x, mid, r, rid);
seg[id] = max(seg[lid], seg[rid]);
}
void add(ll x, ll y, ll l, ll r, ll id)
{
move(l, r, id);
if (l == r - 1)
{
seg[id] += (cnt[l].size() ? (n - *cnt[l].rbegin() - 1) : INF);
cnt[l].insert(y);
seg[id] -= (cnt[l].size() ? (n - *cnt[l].rbegin() - 1) : INF);
return;
}
if (x < mid) add(x, y, l, mid, lid);
else add(x, y, mid, r, rid);
seg[id] = max(seg[lid], seg[rid]);
}
void rem(ll x, ll y, ll l, ll r, ll id)
{
move(l, r, id);
if (l == r - 1)
{
seg[id] += (cnt[l].size() ? (n - *cnt[l].rbegin() - 1) : INF);
cnt[l].erase(y);
seg[id] -= (cnt[l].size() ? (n - *cnt[l].rbegin() - 1) : INF);
return;
}
if (x < mid) rem(x, y, l, mid, lid);
else rem(x, y, mid, r, rid);
seg[id] = max(seg[lid], seg[rid]);
}
vector<ll> countScans(vector<ll> a, vector<ll> xx, vector<ll> vv)
{
ll q = xx.size();
n = a.size();
vector<ll> answer(q);
vector<ll> al;
for (ll x : a) al.push_back(x);
for (ll x : vv) al.push_back(x);
sort(all(al));
al.resize(unique(all(al)) - al.begin());
for (ll i = 0; i < n; i++) a[i] = lower_bound(all(al), a[i]) - al.begin(), cnt[a[i]].insert(i);
for (ll i = 0; i < q; i++) vv[i] = lower_bound(all(al), vv[i]) - al.begin();
ll sum = 0;
for (ll i = al.size() - 1; i >= 0; i--)
{
ma[i] = sum - (cnt[i].size() ? (n - *cnt[i].rbegin() - 1) : INF);
sum += cnt[i].size();
}
build(0, al.size(), 1);
for (ll i = 0; i < q; i++)
{
upd(0, a[xx[i]], -1, 0, al.size(), 1);
rem(a[xx[i]], xx[i], 0, al.size(), 1);
upd(0, vv[i], 1, 0, al.size(), 1);
add(vv[i], xx[i], 0, al.size(), 1);
a[xx[i]] = vv[i];
answer[i] = seg[1];
}
return answer;
}