Submission #1306379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306379		cpismylifeOwO	Roads (CEOI20_roads)	C++20	100 / 100	119 ms	50048 KiB

roads

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
const int MaxLog = 20;

long long Rand(long long l, long long r)
{
    assert(l <= r);
    long long res = 0;
    for (int x = 0; x < 4; x++)
    {
        res = (res << 15) ^ (rand() & ((1ll << 15) - 1));
    }
    return l + res % (r - l + 1);
}

struct Line
{
    long long x1, y1, x2, y2;
    bool isin;

    bool operator < (const Line& other) const
    {
        return this->y1 < other.y1;
    }
};

int n;
Line arr[MaxN];

void Inp()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x].x1 >> arr[x].y1 >> arr[x].x2 >> arr[x].y2;
        if (arr[x].x1 > arr[x].x2 || (arr[x].x1 == arr[x].x2 && arr[x].y1 > arr[x].y2))
        {
            swap(arr[x].x1, arr[x].x2);
            swap(arr[x].y1, arr[x].y2);
        }
        arr[x].isin = false;
    }
    sort(arr + 1, arr + n + 1);
}

struct Vector
{
    long long x, y;

    Vector() = default;

    Vector(long long _x, long long _y)
    {
        x = _x;
        y = _y;
    }

    long long operator * (const Vector& other) const
    {
        return this->x * other.y - this->y * other.x;
    }
};

bool cmp(int a, int b)
{
    assert(arr[a].x1 <= arr[b].x1 && arr[b].x1 <= arr[a].x2);
    if (arr[a].x1 == arr[a].x2)
    {
        return arr[a].y2 < arr[b].y1;
    }
    Vector ca(arr[a].x2 - arr[a].x1, arr[a].y2 - arr[a].y1);
    Vector cb(arr[b].x1 - arr[a].x1, arr[b].y1 - arr[a].y1);
    return (ca * cb > 0);
}

struct Cell;

struct Column
{
    vector<Cell> cells;
    int val;
    long long vx, vy;
};

Column* curpos[MaxN];

struct Cell
{
    Column* prev;
    Column* nxt;

    Cell() = default;

    Cell(Column* _prev, Column* _nxt)
    {
        prev = _prev;
        nxt = _nxt;
    }
};

struct SkipList
{
    Column *head, *tail;

    SkipList()
    {
        head = new Column;
        tail = new Column;
        head->val = tail->val = 0;
        head->vx = head->vy = tail->vx = tail->vy = -1;
        for (int x = 0; x < MaxLog; x++)
        {
            head->cells.push_back(Cell(nullptr, tail));
            tail->cells.push_back(Cell(head, nullptr));
        }
    }

    bool empty()
    {
        return head->cells[0].nxt == tail;
    }

    Column* lower_bound(int v)
    {
        Column* res = head;
        for (int x = MaxLog - 1; x >= 0; x--)
        {
            while (res->cells[x].nxt != tail && !cmp(res->cells[x].nxt->val, v))
            {
                res = res->cells[x].nxt;
            }
        }
        return res;
    }

    void Insert(int v)
    {
        if (arr[v].isin)
        {
            return;
        }
        arr[v].isin = true;
        Column* add = new Column;
        add->val = v;
        add->vx = arr[v].x1;
        add->vy = arr[v].y1;
        add->cells.push_back(Cell(nullptr, nullptr));
        while ((int)add->cells.size() < MaxLog && (Rand(1, 1e9) & 1))
        {
            add->cells.push_back(Cell(nullptr, nullptr));
        }
        Column* pos = head;
        for (int x = MaxLog - 1; x >= 0; x--)
        {
            while (pos->cells[x].nxt != tail && !cmp(pos->cells[x].nxt->val, v))
            {
                pos = pos->cells[x].nxt;
            }
            Column* con = pos->cells[x].nxt;
            if (x < (int)add->cells.size())
            {
                add->cells[x].prev = pos;
                add->cells[x].nxt = con;
                pos->cells[x].nxt = add;
                con->cells[x].prev = add;
            }
        }
        Column* prev = add->cells[0].prev;
        prev->vx = arr[v].x1;
        prev->vy = arr[v].y1;
        if (arr[v].x1 == arr[v].x2)
        {
            prev->vx = arr[v].x2;
            prev->vy = arr[v].y2;
        }
        curpos[v] = add;
    }

    void Delete(int v)
    {
        if (!arr[v].isin)
        {
            return;
        }
        arr[v].isin = false;
        Column* pos = curpos[v];
        pos->cells[0].prev->vx = arr[v].x2;
        pos->cells[0].prev->vy = arr[v].y2;
        for (int x = 0; x < (int)pos->cells.size(); x++)
        {
            Column* prev = pos->cells[x].prev;
            Column* nxt = pos->cells[x].nxt;
            prev->cells[x].nxt = nxt;
            nxt->cells[x].prev = prev;
        }
        curpos[v] = nullptr;
        delete pos;
    }
};

vector<pair<long long, int>> compress;
SkipList ds;

void Print(long long x1, long long y1, long long x2, long long y2)
{
    cout << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
    //cout << "Segment((" << x1 << "," << y1 << "), (" << x2 << "," << y2 << "))\n";
}

void Exc()
{
    for (int x = 1; x <= n; x++)
    {
        compress.push_back(make_pair(arr[x].x1, x));
        compress.push_back(make_pair(arr[x].x2, x + n));
    }
    sort(compress.begin(), compress.end());
    int pre = 0;
    for (int x = 0; x < (int)compress.size(); x++)
    {
        int y = x;
        while (y < (int)compress.size() && compress[x].first == compress[y].first)
        {
            y++;
        }
        y--;
        for (int z = x; z <= y; z++)
        {
            if (compress[z].second <= n)
            {
                int u = compress[z].second;
                //Print(arr[u].x1, arr[u].y1, arr[u].x2, arr[u].y2);
                if (pre > 0 || !ds.empty())
                {
                    if (ds.empty())
                    {
                        Print(arr[pre].x2, arr[pre].y2, arr[u].x1, arr[u].y1);
                    }
                    else
                    {
                        Column* res = ds.lower_bound(u);
                        if (res == ds.head && !(~ds.head->vx))
                        {
                            res = res->cells[0].nxt;
                            Print(arr[res->val].x1, arr[res->val].y1, arr[u].x1, arr[u].y1);
                        }
                        else
                        {
                            Print(res->vx, res->vy, arr[u].x1, arr[u].y1);
                        }
                    }
                }
                ds.Insert(u);
                //cout << "\n";
            }
            else
            {
                int u = compress[z].second - n;
                pre = u;
                ds.Delete(u);
            }
        }
        x = y;
    }
}

int main()
{
    //freopen("ROADS.INP", "r", stdin);
    //freopen("ROADS.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(nullptr));
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40