Submission #354332

#	Time	Username	Problem	Language	Result	Execution time	Memory
354332		Frankenween	Exercise Deadlines (CCO20_day1problem2)	C++17	0 / 25	2 ms	748 KiB

Main

#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 (stderr)

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()) {
      |                ~~^~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 8