#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds//tree_policy.hpp>
//#define _FORTIFY_SOURCE 0
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-falign-jumps")
//#pragma GCC optimize("-falign-loops")
//#pragma GCC optimize("-falign-labels")
//#pragma GCC optimize("-fdevirtualize")
//#pragma GCC optimize("-fcaller-saves")
//#pragma GCC optimize("-fcrossjumping")
//#pragma GCC optimize("-fthread-jumps")
//#pragma GCC optimize("-funroll-loops")
//#pragma GCC optimize("-fwhole-program")
//#pragma GCC optimize("-freorder-blocks")
//#pragma GCC optimize("-fschedule-insns")
//#pragma GCC optimize("inline-functions")
//#pragma GCC optimize("-ftree-tail-merge")
//#pragma GCC optimize("-fschedule-insns2")
//#pragma GCC optimize("-fstrict-aliasing")
//#pragma GCC optimize("-fstrict-overflow")
//#pragma GCC optimize("-falign-functions")
//#pragma GCC optimize("-fcse-skip-blocks")
//#pragma GCC optimize("-fcse-follow-jumps")
//#pragma GCC optimize("-fsched-interblock")
//#pragma GCC optimize("-fpartial-inlining")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("-freorder-functions")
//#pragma GCC optimize("-findirect-inlining")
//#pragma GCC optimize("-fhoist-adjacent-loads")
//#pragma GCC optimize("-frerun-cse-after-loop")
//#pragma GCC optimize("inline-small-functions")
//#pragma GCC optimize("-finline-small-functions")
//#pragma GCC optimize("-ftree-switch-conversion")
//#pragma GCC optimize("-foptimize-sibling-calls")
//#pragma GCC optimize("-fexpensive-optimizations")
//#pragma GCC optimize("-funsafe-loop-optimizations")
//#pragma GCC optimize("inline-functions-called-once")
//#pragma GCC optimize("-fdelete-null-pointer-checks")
#define ull unsigned long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef std::complex<ld> cmpl;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const ll P1 = 678463;
const ll P2 = 239;
const ll inf = (ll)1e18;
const long double MATH_E = 2.718281828459;
const long double eps = 1e-9;
const long double MATH_PI = atan2l(0, -1);
using namespace std;
using namespace __gnu_pbds;
template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
for (T &cnt : arr) {
in >> cnt;
}
return in;
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) {
std::uniform_int_distribution<ll> range(l, r);
return range(rng);
}
struct finder {
set<int, less<>> after;
set<int, greater<>> before;
void replace(int p) {
before.erase(p);
after.insert(p);
}
void addBefore(int p) {
before.insert(p);
}
void addAfter(int p) {
after.insert(p);
}
int get() {
if (!after.empty()) {
int res = *after.begin();
after.erase(after.begin());
return res;
}
if (!before.empty()) {
int res = *before.begin();
before.erase(before.begin());
return res;
}
return -1;
}
};
struct fenw {
vector<int> f;
void add(int x) {
while (x < f.size()) {
f[x]++;
x |= (x + 1);
}
}
int sum(int x) {
int res = 0;
while (x >= 0) {
res += f[x];
x = ((x + 1) & x) - 1;
}
return res;
}
};
void solve() {
int n;
cin >> n;
vector<vector<int>> sameD(n);
vector<int> arr(n);
for (int i = 0; i < n; i++) {
int d;
cin >> d;
d--;
arr[i] = d;
sameD[d].pb(i);
}
vector<int> answer(n);
finder f;
vector<int> used(n);
for (int i = n - 1; i >= 0; i--) {
for (auto p : sameD[i]) {
if (p >= i) {
f.addAfter(p);
} else {
f.addBefore(p);
}
}
if (arr[i] >= i and !used[i]) {
f.replace(i);
}
int x = f.get();
if (x < 0 or x > n) {
cout << -1;
return;
}
answer[i] = x;
used[x] = 1;
}
ll ans = 0;
fenw ft;
ft.f.resize(n);
for (int i = n - 1; i >= 0; i--) {
ans += ft.sum(answer[i]);
ft.add(answer[i]);
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cout.precision(30);
srand(time(0));
cout.setf(ios::fixed);
solve();
return 0;
}
Compilation message
Main.cpp: In member function 'void fenw::add(int)':
Main.cpp:140:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | while (x < f.size()) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
