/**
* author: Haunted_Cpp
**/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif
class FenwickTree {
private:
const int L;
vector<int> bit;
public:
FenwickTree(int n) : L(n + 5) {
bit.clear();
bit.resize(L);
}
void update(int idx, int delta) {
for (; idx < L; idx += idx & (- idx)) {
bit[idx] += delta;
}
}
void range_update(int lo, int hi, int delta) {
update(lo, +delta);
update(hi + 1, -delta);
}
int query(int idx) {
int res = 0;
for(; idx > 0; idx -= idx & (-idx)) {
res += bit[idx];
}
return res;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> arr(n + 1);
vector<vector<int>> where(n + 1);
vector<int> ord(n);
set<int> idx;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
idx.insert(i);
ord[i - 1] = arr[i];
where[arr[i]].emplace_back(i);
}
sort(ord.begin(), ord.end());
ord.erase(unique(ord.begin(), ord.end()), ord.end());
FenwickTree fen(n + 1);
long long res = 0;
auto find_next = [&](int delta) {
auto best = idx.upper_bound(delta);
if (best == idx.begin()) return -1;
return *(prev(best));
};
for (auto cur : ord) {
int best_way = cur;
for (auto to : where[cur]) {
int idx_inicial = to;
int idx_real = idx_inicial + fen.query(idx_inicial);
if (idx_real < best_way) continue;
int where_to_put = find_next(best_way);
if (where_to_put == -1) {
cout << -1 << '\n';
return 0;
}
fen.range_update(1, idx_inicial, +1);
res += idx_real - best_way;
--best_way;
}
}
cout << res << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
