Submission #362704

#	Time	Username	Problem	Language	Result	Execution time	Memory
362704		alextodoran	Exercise Deadlines (CCO20_day1problem2)	C++17	25 / 25	232 ms	13548 KiB

Main

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200002;

int n;

int d[N_MAX];

int p[N_MAX];

set <int> s;

int BIT[N_MAX];

void update (int pos)
{
    for(int i = pos; i >= 1; i -= i & -i)
        BIT[i]++;
}

int query (int pos)
{
    int ans = 0;
    for(int i = pos; i <= n; i += i & -i)
        ans += BIT[i];
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> d[i];
    for(int i = 1; i <= n; i++)
        s.insert(i);
    for(int i = n; i >= 1; i--)
    {
        set <int> :: iterator it = s.upper_bound(d[i]);
        if(it == s.begin())
        {
            cout << "-1\n";
            return 0;
        }
        it--;
        p[i] = *it;
        s.erase(it);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans += query(p[i]);
        update(p[i]);
    }
    cout << ans << "\n";
    return 0;
}

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