Submission #765539

#	Time	Username	Problem	Language	Result	Execution time	Memory
765539		boris_mihov	Seats (IOI18_seats)	C++17	11 / 100	3775 ms	89300 KiB

seats

#include "seats.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int INF  = 1e9;

int h, w;
struct Point
{
    int x, y;
};

struct SegmentTree
{
    int tree[2*MAXN];
    virtual int cmp(int x, int y)
    {
        assert(false);
    }

    virtual bool inSearch(int x, int y)
    {
        assert(false);
    }

    void build(int l, int r, int node, int vals[])
    {
        if (l == r)
        {
            tree[node] = vals[l];
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, vals);
        build(mid + 1, r, 2*node + 1, vals);
        tree[node] = cmp(tree[2*node], tree[2*node + 1]);
    }

    void update(int l, int r, int node, int queryPos, int queryVal)
    {
        if (l == r)
        {
            tree[node] = queryVal;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
        else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
        tree[node] = cmp(tree[2*node], tree[2*node + 1]);
    }

    int searchFirst(int l, int r, int node, int value)
    {
        if (l == r)
        {
            return l;
        }

        int mid = (l + r) / 2;
        if (inSearch(tree[2*node], value)) return searchFirst(l, mid, 2*node, value);
        return searchFirst(mid + 1, r, 2*node + 1, value);
    }

    void update(int pos, int val)
    {
        update(1, h * w + 1, 1, pos, val);
    }

    int searchFirst(int value)
    {
        return searchFirst(1, h * w + 1, 1, value);
    }

    void build(int vals[])
    {
        build(1, h * w + 1, 1, vals);
    }
};

struct SegmentTreeMAX : SegmentTree
{
    int cmp(int x, int y) override
    {   
        return std::max(x, y);
    };

    bool inSearch(int x, int y) override
    {
        return x > y;
    };
};

struct SegmentTreeMIN : SegmentTree
{
    int cmp(int x, int y) override
    {   
        return std::min(x, y);
    };

    bool inSearch(int x, int y) override
    {
        return x < y;
    };
};

Point p[MAXN];
int vals[MAXN];
SegmentTreeMIN minX, minY;
SegmentTreeMAX maxX, maxY;

void give_initial_chart(int H, int W, std::vector <int> R, std::vector <int> C)
{
    h = H;
    w = W;
    for (int i = 0 ; i < H * W ; ++i)
    {
        p[i + 1] = {R[i] + 1, C[i] + 1};
    }

    for (int i = 1 ; i <= h * w ; ++i)
    {
        vals[i] = p[i].x;
    }

    vals[h * w + 1] = 0;
    minX.build(vals);
    vals[h * w + 1] = INF;
    maxX.build(vals);

    for (int i = 1 ; i <= h * w ; ++i)
    {
        vals[i] = p[i].y;
    }

    vals[h * w + 1] = 0;
    minY.build(vals);
    vals[h * w + 1] = INF;
    maxY.build(vals);
}

void fixPoint(int idx)
{
    minX.update(idx, p[idx].x);
    maxX.update(idx, p[idx].x);
    minY.update(idx, p[idx].y);
    maxY.update(idx, p[idx].y);
}

int swap_seats(int a, int b) 
{
    std::swap(p[a + 1], p[b + 1]);
    fixPoint(a + 1);
    fixPoint(b + 1);

    int ans = 1;
    int minRow = INF, minCol = INF;
    int maxRow = -INF, maxCol = -INF;
    int sz = 0;

    while (sz < h * w)
    {
        int firstMinX = minX.searchFirst(minRow);
        int firstMaxX = maxX.searchFirst(maxRow);
        int firstMinY = minY.searchFirst(minCol);
        int firstMaxY = maxY.searchFirst(maxCol);
        int first = std::min(std::min(firstMinX, firstMaxX), std::min(firstMinY, firstMaxY));
        
        if (sz && first == sz + 1)
        {
            ans++;
        }

        minRow = std::min(minRow, p[first].x);
        maxRow = std::max(maxRow, p[first].x);
        minCol = std::min(minCol, p[first].y);
        maxCol = std::max(maxCol, p[first].y);
        sz = (maxRow - minRow + 1) * (maxCol - minCol + 1);
    }

    return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30