#include <bits/stdc++.h>
namespace std
{
template <class Fun>
class y_combinator_result
{
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
template <class... Args>
decltype(auto) operator()(Args &&... args)
{
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun>
decltype(auto) y_combinator(Fun &&fun)
{
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
} // namespace std
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;
#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second
clock_t time_p = clock();
void time_taken()
{
time_p = clock() - time_p;
cerr << "Time Taken : " << (float)(time_p) / CLOCKS_PER_SEC << "\n";
}
const ll mod = 1e9 + 7;
const ll INF = 1e18;
#include <bits/extc++.h>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// s.order_of_key(x) -> Number of elements in s strictly smaller than x
// auto it = s.find_by_order(k) -> iterator to the kth smallest element(0-indexed)
struct BIT
{
vector<long long> bit;
BIT(int n = 1e5 + 6) : bit(n)
{
}
void update(int x, int v)
{
while (x < int(bit.size()))
{
bit[x] += v;
x += (x & -x);
}
}
long long query(int x)
{
long long sum = 0;
while (x > 0)
{
sum += bit[x];
x -= (x & -x);
}
return sum;
}
void upd_range(int l, int r, int v)
{
update(l, v);
update(r + 1, -v);
}
long long query_range(int l, int r)
{
return query(r) - query(l - 1);
}
};
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
BIT b(n + 10);
ll ans = 0;
std::y_combinator([&](auto self) -> vi {
int p;
cin >> p;
vi ret;
if (p)
{
ans += b.query(n) - b.query(p);
b.update(p, 1);
ret.pb(p);
return ret;
}
ret = self();
auto foo = self();
if (sz(ret) < sz(foo))
{
ll i1 = 0, i2 = 0;
for (auto x : ret)
{
b.update(x, -1);
}
for (auto x : ret)
{
int lt = b.query(x);
int gt = sz(foo) - lt;
i1 += lt;
i2 += gt;
}
ans -= max<ll>(i1 - i2, 0LL);
for (auto x : ret)
{
b.update(x, 1);
foo.pb(x);
}
return foo;
}
else
{
for (auto x : foo)
{
b.update(x, -1);
}
ll i1 = 0, i2 = 0;
for (auto x : foo)
{
int lt = b.query(x);
int gt = sz(ret) - lt;
i1 += gt;
i2 += lt;
}
ans -= max<ll>(i1 - i2, 0);
for (auto x : foo)
{
b.update(x, +1);
ret.pb(x);
}
return ret;
}
})();
cout << ans << endl;
time_taken();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
1296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
17472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
11084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
6992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
6140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
