| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 215922 | balbit | Bubble Sort 2 (JOI18_bubblesort2) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#endif // BALBIT
const int maxn = 1e6+5;
multiset <int> pos[maxn];
int tag[maxn*4], s[maxn*4];
void push(int o, int l, int r){
if (!tag[o]) return;
s[o]+=tag[o];
if (l!=r){
tag[o*2+1]+=tag[o];
tag[o*2+2]+=tag[o];
}
tag[o]=0;
}
int MX;
void MO(int L, int R, int v, int o=0, int l=0, int r=MX-1){
push(o,l,r);
if (l>R||r<L) return;
if (l>=L&&r<=R) {
tag[o]+=v; push(o,l,r); return;
}
int mid = (l+r)/2;
MO(L,R,v, o*2+1,l,mid);
MO(L,R,v, o*2+2,mid+1,r);
s[o]=min(s[o*2+1],s[o*2+2]);
}
inline int big(multiset<int> & ms) {
return SZ(ms)?-*(ms.rbegin()):0;
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
int Q=X.size();
vector<int> answer(Q);
int n = SZ(A);
vector<int> tmp = A;
for (int x : V) tmp.pb(x);
SORT_UNIQUE(tmp);
MX = SZ(tmp);
for (int i = 0; i<n; ++i) {
A[i] = lower_bound(ALL(tmp), A[i]) - tmp.begin();
pos[A[i]].insert(i);
MO(A[i]+1, MX-1,1);
}
for (int i = 0; i<Q; ++i) {
V[i] = lower_bound(ALL(tmp), V[i]) - tmp.begin();
}
for (int i = 0; i<n; ++i) {
if (big(pos[A[i]]) == -i) {
MO(A[i],A[i],-i);
}
}
bug(s[0]);
for (int cnt = 0; cnt<Q; ++cnt) {
int i = X[cnt];
MO(A[i]+1, MX-1, -1);
MO(A[i], A[i],-big(pos[A[i]]));
bug(A[i], i);
pos[A[i]].erase(pos[A[i]].find(i));
MO(A[i],A[i], big(pos[A[i]]));
A[i] = V[cnt];
bug("insert",A[i],i);
MO(A[i]+1, MX-1, 1);
MO(A[i],A[i], -big(pos[A[i]]));
pos[A[i]].insert(i);
MO(A[i], A[i],big(pos[A[i]]));
answer[cnt] = -s[0];
}
return answer;
}
#ifdef BALBIT
signed main(){
IOS();
vector<int> mo = (countScans({1,2,3,4},{0,2},{3,1}));
for (int x : mo) bug(x);
}
#endif