Untitled

#include<iostream>
#include<vector>
#include<unordered_map>
#include<set>
#include<iterator>
 
using namespace std;
struct comp {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) const{
        if ((a.second - a.first) > (b.second - b.first))
            return true;
        else if (a.second - a.first == b.second - b.first)
            return(a.first < b.first);
        else
            return false;
    }
};
 
int n;
set<pair<int, int>, comp> empty_space;
set<pair<int, int>> interval;
unordered_map<int, int> building;
 
 
 
void init(int N) {
    n = N;
    empty_space.clear();
    building.clear();
    interval.clear();
    empty_space.insert({ 0,N - 1 });
    interval.insert({ 0,N - 1 });
}
 
 
int build(int mLength) {
    int address;
    set<pair<int, int>, comp> ::iterator it = empty_space.begin();
    int start = it->first;
    int end = it->second;
    int spacelength = end - start +1 ;
    if (spacelength < mLength)
        return -1;
    address = start + ((spacelength - mLength) / 2);
    building[address] = mLength;
 
    empty_space.erase({ start,end });
    interval.erase({ start,end });
 
    empty_space.insert({ start, address - 1 });
    empty_space.insert({ address + mLength,end });
 
    interval.insert({ start, address - 1 });
    interval.insert({ address + mLength,end });
 
    return address;
}
 
int demolish(int mAddr) {
 
 
    if (building.find(mAddr) != building.end()) {
        int length = building[mAddr];
        int new_start, new_end;
        building.erase(mAddr);
        int start = mAddr;
        int end = mAddr + length - 1;
 
        if (empty_space.empty()) {
            empty_space.insert({ start,end });
            interval.insert({ start,end });
 
            return length;
        }
        set<pair<int, int>> ::iterator it1 = interval.lower_bound({ start,end });
        set<pair<int, int>> ::iterator it2 = interval.upper_bound({ start,end });
 
        it1--;
 
        if (it1 == interval.begin()) {
            new_start = 0;
        }
        else
        {
            if (it1->second + 1 == start) {
                new_start = it1->first;
                //empty_space.erase(*it1);
                //interval.erase(*it1);
            }
            else {
                new_start = start;
            }
        }
 
        if (it2 == interval.end()) {
            new_end = n - 1;
        }
 
        else {
            if (it2->first - 1 == end) {
                new_end = it2->second;
 
                //empty_space.erase(*it2);
                //interval.erase(*it2);
            }
            else {
                new_end = end;
            }
             
        }
        empty_space.erase(*it1);
        interval.erase(*it1);
        empty_space.erase(*it2);
        interval.erase(*it2);
 
 
         
         
 
        empty_space.insert({ new_start,new_end });
        interval.insert({ new_start,new_end });
 
        return length;
    }
 
 
    else
    {
        return -1;
    }
 
}

/*
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>
//#include <iostream>
//using namespace std;

extern void init(int N);
extern int build(int mLength);
extern int demolish(int mAddr);

#define CMD_INIT 1
#define CMD_BUILD 2
#define CMD_DEMOLISH 3

static bool run()
{
    int query_num;
    scanf("%d", &query_num);

    int ans;
    bool ok = false;

    for (int q = 0; q < query_num; q++)
    {
        int query;
        scanf("%d", &query);
        if (query == CMD_INIT)
        {
            int N;
            scanf("%d", &N);
            init(N);
            ok = true;
        }
        else if (query == CMD_BUILD)
        {
            int mLength;
            scanf("%d", &mLength);
            int ret = build(mLength);
            scanf("%d", &ans);
            if (ans != ret)
            {
				//cout<<"Ret: "<<ret<<" "<<ans<<endl;
                ok = false;
            }
        }
        else if (query == CMD_DEMOLISH)
        {
            int mAddr;
            scanf("%d", &mAddr);
            int ret = demolish(mAddr);
            scanf("%d", &ans);
            if (ans != ret)
            {
                ok = false;
            }
        }
    }
    return ok;
}

int main()
{
    setbuf(stdout, NULL);
    freopen("sample_input.txt", "r", stdin);
    int T, MARK;
    scanf("%d %d", &T, &MARK);
    for (int tc = 1; tc <= T; tc++)
    {
        int score = run() ? MARK : 0;
        printf("#%d %d\n", tc, score);
    }
    return 0;
}
1 100
20
1 30
2 7 11
2 5 21
2 11 0
2 4 26
2 3 18
2 5 -1
3 0 11
2 10 0
3 11 7
3 21 5
3 18 3
3 18 -1
3 2 -1
2 8 14
2 3 10
2 5 -1
3 10 3
3 26 4
3 10 -1
*/