| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 67230 | Kubalionzzale | Bubble Sort 2 (JOI18_bubblesort2) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bubblesort2.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
int n;
int a[500010];
std::vector< std::pair<int, int> > valsSorted(1000010);
int plused[1000010];
long long int segTreeused[8000010];
long long int segTreeunused[8000010];
long long int lazy[8000010] = { 0 };
std::map< int, int> mapa;
void construct(int low, int high, int pos)
{
if (low == high)
{
if (a[valsSorted[low].second] == valsSorted[low].first)
{
segTreeused[pos] = plused[low] * 1LL;
segTreeunused[pos] = -1e15 * 1LL;
}
else
{
segTreeunused[pos] = plused[low] * 1LL;
segTreeused[pos] = -1e15 * 1LL;
}
//std::cout << low << ":" << high << ", unused: " << segTreeunused[pos] << "|used: " << segTreeused[pos] << "\n";
return;
}
int mid = low + (high - low) / 2;
construct(low, mid, pos * 2 + 1);
construct(mid + 1, high, pos * 2 + 2);
segTreeunused[pos] = std::max(segTreeunused[pos * 2 + 1], segTreeunused[pos * 2 + 2]);
segTreeused[pos] = std::max(segTreeused[pos * 2 + 1], segTreeused[pos * 2 + 2]);
// std::cout << low << ":" << high << ", unused: " << segTreeunused[pos] << "|used: " << segTreeused[pos] << "\n";
}
void update(int low, int high, int qlow, int qhigh, int val, int pos)
{
segTreeunused[pos] += lazy[pos] * 1LL;
segTreeused[pos] += lazy[pos] * 1LL;
if (low != high)
{
lazy[pos * 2 + 1] += lazy[pos] * 1LL;
lazy[pos * 2 + 2] += lazy[pos] * 1LL;
}
lazy[pos] = 0LL;
if (low > qhigh || high < qlow)
return;
if (qlow <= low && high <= qhigh)
{
lazy[pos] += val * 1LL;
segTreeunused[pos] += lazy[pos] * 1LL;
segTreeused[pos] += lazy[pos] * 1LL;
if (low != high)
{
lazy[pos * 2 + 1] += lazy[pos] * 1LL;
lazy[pos * 2 + 2] += lazy[pos] * 1LL;
}
lazy[pos] = 0LL;
// std::cout << low << ":" << high << ", unused: " << segTreeunused[pos] << "|used: " << segTreeused[pos] << "\n";
return;
}
int mid = low + (high - low) / 2;
update(low, mid, qlow, qhigh, val, pos * 2 + 1);
update(mid + 1, high, qlow, qhigh, val, pos * 2 + 2);
segTreeunused[pos] = std::max(segTreeunused[pos * 2 + 1], segTreeunused[pos * 2 + 2]);
segTreeused[pos] = std::max(segTreeused[pos * 2 + 1], segTreeused[pos * 2 + 2]);
//std::cout << low << ":" << high << ", unused: " << segTreeunused[pos] << "|used: " << segTreeused[pos] << "\n";
// std::cout << low << " " << high << " " << segTreeunused[pos] << " " << segTreeused[pos] << "\n";
}
void makeunused(int low, int high, int node, int pos)
{
segTreeunused[pos] += lazy[pos] * 1LL;
segTreeused[pos] += lazy[pos] * 1LL;
if (low != high)
{
lazy[pos * 2 + 1] += lazy[pos] * 1LL;
lazy[pos * 2 + 2] += lazy[pos] * 1LL;
}
lazy[pos] = 0LL;
if (node > high || node < low)
return;
if (node <= low && high <= node)
{
std::swap(segTreeunused[pos], segTreeused[pos]);
return;
}
int mid = low + (high - low) / 2;
makeunused(low, mid, node, pos * 2 + 1);
makeunused(mid + 1, high, node, pos * 2 + 2);
segTreeunused[pos] = std::max(segTreeunused[pos * 2 + 1], segTreeunused[pos * 2 + 2]);
segTreeused[pos] = std::max(segTreeused[pos * 2 + 1], segTreeused[pos * 2 + 2]);
// std::cout << low << "|" << high << "|" << segTreeunused[pos] << "|" << segTreeused[pos] << "\n";
}
std::vector<int> count_scans(std::vector<int> A,std::vector<int> x,std::vector<int> val){
int q=x.size();
n = A.size();
std::vector<int> answer(q + 5);
for (int i = 0; i < n; ++i)
{
mapa.insert(std::make_pair(A[i], 0));
}
for (int i = 0; i < q; ++i)
{
mapa.insert(std::make_pair(val[i], 0));
}
int cnt = 0;
for (auto it = mapa.begin(); it != mapa.end(); ++it)
{
it -> second = cnt;
++cnt;
}
for (int i = 0; i < n; ++i)
{
a[i] = mapa[A[i]];
}
for (int i = 0; i < q; ++i)
{
val[i] = mapa[val[i]];
}
mapa.clear();
for (int i = 0; i < n; ++i)
{
valsSorted[i].first = a[i];
valsSorted[i].second = i;
}
for (int i = 0; i < q; ++i)
{
valsSorted[n + i].first = val[i];
valsSorted[n + i].second = x[i];
}
std::sort(valsSorted.begin() , valsSorted.begin() + n + q);
auto last = std::unique(valsSorted.begin() , valsSorted.begin() + n + q);
valsSorted.erase(last, valsSorted.end() );
cnt = 0;
for (int i = 0; i < valsSorted.size(); ++i)
{
plused[i] = valsSorted[i].second - cnt;
// std::cout << valsSorted[i].first << " " << valsSorted[i].second << "\n";
if (a[valsSorted[i].second] == valsSorted[i].first)
++cnt;
}
int siz = valsSorted.size();
construct(0, siz - 1, 0);
for (int i = 0; i < q; ++i)
{
// std::cout << "\n\n\n";
if (a[x[i]] == val[i])
continue;
int two = lower_bound(valsSorted.begin(), valsSorted.end(), std::make_pair(val[i], x[i])) - valsSorted.begin();
int one = lower_bound(valsSorted.begin(), valsSorted.end(), std::make_pair(a[x[i]], x[i])) - valsSorted.begin();
a[x[i]] = val[i];
if (one < two)
{
// std::cout << segTreeunused[11] << "qwe" << segTreeused[11] << "\n";
makeunused(0, siz - 1, one, 0);
// std::cout << segTreeunused[11] << "qwe" << segTreeused[11] << "\n";
makeunused(0, siz - 1, two, 0);
// std::cout << segTreeunused[11] << "qwe" << segTreeused[11] << "\n";
update(0, siz - 1, one + 1, two, 1LL, 0);
// std::cout << segTreeunused[11] << "qwe" << segTreeused[11] << "\n";
}
else
{
makeunused(0, siz - 1, one, 0);
makeunused(0, siz - 1, two, 0);
update(0, siz - 1, two + 1, one, -1 * 1LL, 0);
}
answer[i] = segTreeused[0];
}
return answer;
}