Submission #577940

#	Time	Username	Problem	Language	Result	Execution time	Memory
577940		MohamedFaresNebili	Exercise Deadlines (CCO20_day1problem2)	C++14	25 / 25	242 ms	15460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
    vector<vector<int> > l;

vector<int> s;
int t[800005];
int sum(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && r == tr) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, min(r, tm))
           + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] += new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = t[v*2] + t[v*2+1];
    }
}

int main(){
    int n;
    cin >> n;
    l.resize(n+1);
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        s.push_back(a);
        l[a].push_back(i);
        update(1,0,n-1,i,1);
    }
    priority_queue<int> q;
    long long res = 0;
    for(int i = n-1; i >= 0; i--){
        for(int j=0;j<l[i+1].size();j++)
        {
            q.push(l[i+1][j]);
        }
        if(q.empty())
        {
            cout << -1 << endl;
            return 0;
        }
        int u=q.top();
        q.pop();
      //  cout << res << endl;
        int j = sum(1,0,n-1,0,u);
        res += i-j+1;
        update(1,0,n-1, u,-1);
    }
    cout << res << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j=0;j<l[i+1].size();j++)
      |                     ~^~~~~~~~~~~~~~

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