| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 146210 | nicolaalexandra | Bubble Sort 2 (JOI18_bubblesort2) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <fstream>
#include <algorithm>
#include <vector>
#define DIM 500010
#define INF 2000000000
using namespace std;
vector <long long> a,x,v;
pair <long long,long long> aint[4*DIM];
long long w[DIM*2],qry[DIM];
void lazy (int nod, int st, int dr){
if (!aint[nod].second)
return;
aint[nod].first += aint[nod].second;
if (st != dr){ /// nu e frunza
aint[nod<<1].second += aint[nod].second;
aint[(nod<<1)|1].second += aint[nod].second;
}
aint[nod].second = 0;
}
void update (int nod, int st, int dr, int x, int y, long long val){
lazy (nod,st,dr);
if (st > dr || y < st || x > dr)
return;
if (x <= st && dr <= y){
aint[nod].second += val;
lazy (nod,st,dr);
return;
}
int mid = (st+dr)>>1;
update (nod<<1,st,mid,x,y,val);
update ((nod<<1)|1,mid+1,dr,x,y,val);
aint[nod].first = max (aint[nod<<1].first,aint[(nod<<1)|1].first);
}
inline int cautare_binara (long long v[], int n, long long val){
int st = 1, dr = n;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[mid] == val)
return mid;
if (v[mid] < val)
st = mid+1;
else dr = mid-1;
}}
vector <int> countScans (vector <long long> a, vector <long long> x, vector <long long> v){
int k = 0, n = a.size(), q = v.size();
for (int i=0;i<n;i++){
a[i] = a[i]*(n+1)+i; /// fac asta ca sa obtin elemente distincte pe care dupa le normalizez
w[++k] = a[i];
}
for (int i=0;i<q;i++){
qry[i] = v[i]*(n+1)+x[i];
w[++k] = qry[i];
}
sort (w+1,w+k+1);
int k2 = 1;
for (int i=2;i<=k;i++)
if (w[i] != w[i-1])
w[++k2] = w[i];
k = k2;
update (1,1,k,1,k,-INF); /// initializez cu -INF, apoi adaug INF+i
/// starea initiala
for (int i=0;i<n;i++){
int val = cautare_binara(w,k,a[i]);
update (1,1,k,val,val,INF+i); /// am i puncte mai mici decat el in stanga lui
update (1,1,k,1,val,1);
}
vector <int> sol;
for (int i=0;i<q;i++){
int poz = cautare_binara (w,k,a[x[i]]);
update (1,1,k,1,poz,-1);
update (1,1,k,poz,poz,-INF-x[i]);
a[x[i]] = qry[i];
poz = cautare_binara (w,k,qry[i]);
update (1,1,k,poz,poz,INF+x[i]);
update (1,1,k,1,poz,1);
sol.push_back(aint[1].first - n);
}
return sol;
}