Submission #272740

#TimeUsernameProblemLanguageResultExecution timeMemory
272740Haunted_CppExercise Deadlines (CCO20_day1problem2)C++17
0 / 25
3 ms768 KiB
/** * 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...