Key cutting

#include<iostream>
#include<vector>
#include <cmath>
#include<list>
#include<queue> 
#include<climits> 

using namespace std;


struct vless : std::binary_function<vector<int>, vector<int>, bool>
{
    bool operator()(const vector<int>& a, const vector<int> &b) const { return a[0] < b[0]; }
};

int main()
{
    int n = 0;
    cin >> n;

    //vector<int> segs = {1, 0, 1, 1, 0, 2, 1, 3, 3, 1, 2, 3, 4, 0};
//    vector<int> segs = {1, 0, 1, 1, 0, 2, 1, 3, 3, 1};

    vector<vector<int> > sdata;

    priority_queue<vector<int>, vector<vector<int> >, vless> q;
    

    int prev = -1;
    int prev_d = -1;

    for(int i = 0; i < n; ++i)
    //for(size_t i = 0; i < size(segs); ++i)
    {
        //int d = segs[i];
        int d = 0;
        cin >> d;
        vector<int> sitem = vector<int>({-1, -1, -1});
        sitem[0] = d;

        if(prev_d != d)
        {
            sitem[1] = prev;
            if(prev >= 0)
                sdata[prev][2] = i;
            prev = i;
            prev_d = d;
            // cout << "DEBUG HEAP i" << i << " " << d << endl;
            if(d > 0)
                q.push({d, int(i)});
        }

        sdata.push_back(sitem);
    }

//    for(size_t i = 0; i < size(sdata); ++i)
  //      cout << sdata[i][0] << " " << sdata[i][1] << " " << sdata[i][2] << endl;

    int n_ops = 0;
    while(!q.empty())
    {
    //    cout << q.top()[0] << " i: " << q.top()[1] << endl;
        int i = q.top()[1];

        auto val = sdata[i][0];
        if(val < 0)
        {
//            cout << "DISC" << endl;
            q.pop();
            continue;
        }

        auto prev_i = sdata[i][1];
        auto next_i = sdata[i][2];

      //  cout << "UPDATE " << "i " << i << " prev_i " << i <<  " next_i " << next_i <<endl;
        auto prev_val = prev_i >= 0 ? sdata[prev_i][0] : INT_MAX;
        auto next_val = next_i >= 0 ? sdata[next_i][0] : INT_MAX;

        auto update_val = min(prev_val, next_val);

        if(update_val < val)
        {
            sdata[i][0] = -1;
            sdata[i][1] = -1;
            sdata[i][1] = -1;
            if(prev_i > 0)
                sdata[prev_i][2] = next_i;
            if(next_i > 0)
                sdata[next_i][1] = prev_i;

            if(prev_val == next_val && prev_val > 0)
            {
                int supernext_i = sdata[next_i][2];
                if(prev_i > 0)
                   sdata[prev_i][2] = supernext_i;
                if(supernext_i > 0)
                   sdata[supernext_i][1] = prev_i;

                sdata[next_i][0] = -1;
                sdata[next_i][1] = -1;
                sdata[next_i][1] = -1;
            }
        }

        //sdata[i]

        q.pop();
        ++n_ops;

    }
    cout << n_ops << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED