Submission #1010983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010983		boris_mihov	Seats (IOI18_seats)	C++17	0 / 100	4094 ms	234936 KiB

seats

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

typedef long long llong;
const int MAXN = 1 << 20;
const int INF  = 1e9;

int n, m;
struct SegmentTreeLazy
{
    struct Node
    {
        int min;
        int cnt;
        int lazy;
        
        Node()
        {
            min = cnt = lazy = 0;
        }
    
        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            res.min = std::min(left.min, right.min);
            if (res.min == left.min) res.cnt += left.cnt;
            if (res.min == right.min) res.cnt += right.cnt;
            return res;
        }
    };

    Node tree[2*MAXN];
    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].min = 0;
            tree[node].cnt = 1;
            return;
        }

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

    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        tree[node].min += tree[node].lazy;
        if (l < r)
        {
            tree[2*node].lazy += tree[node].lazy;
            tree[2*node + 1].lazy += tree[node].lazy;
        }

        tree[node].lazy = 0;
    }

    void update(int l, int r, int node, int queryL, int queryR, int queryVal)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy = queryVal;
            push(node, l, r);
            return;
        }

        int mid = l + r >> 1;
        update(l, mid, 2*node, queryL, queryR, queryVal);
        update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        Node res; res.min = INF;
        int mid = l + r >> 1;

        if (queryL <= mid) res = res + query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) res = res + query(mid + 1, r, 2*node + 1, queryL, queryR);
        return res;
    }

    void build()
    {
        build(1, n * m, 1);
    }

    void update(int l, int r, int val)
    {
        // std::cout << "singular update: " << l << ' ' << r << ' ' << val << '\n';
        update(1, n * m, 1, l, r, val);
    }

    int query(int l, int r, int value)
    {
        Node res = query(1, n * m, 1, l, r);
        // std::cout << "reeeessss: " << res.min << ' ' << res.cnt << '\n';
        if (res.min != value) return 0;
        return res.cnt;
    }
};

struct SegmentTreeMinMax
{
    struct Node
    {
        int min;
        int max;
        
        Node()
        {
            min = INF;
            max = 0;
        }
    
        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            res.min = std::min(left.min, right.min);
            res.max = std::max(left.max, right.max);
            return res;
        }
    };

    Node tree[2*MAXN];
    void build(int l, int r, int node, std::vector <int> &v)
    {
        if (l == r)
        {
            // std::cout << "set: " << l << " = " << v[l] << '\n';
            tree[node].min = tree[node].max = v[l];
            return;
        }

        int mid = l + r >> 1;
        build(l, mid, 2*node, v);
        build(mid + 1, r, 2*node + 1, v);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

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

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

    int search(int l, int r, int node, int value)
    {
        if (l == r)
        {
            if (tree[node].min != value) return -1;
            return l;
        }

        int mid = l + r >> 1;
        if (tree[2*node].min == value && tree[2*node].max == value)
        {
            int res = search(mid + 1, r, 2*node + 1, value);
            if (res != -1) return res;
            return mid;
        }

        return search(l, mid, 2*node, value);
    }

    void build(std::vector <int> &v)
    {
        build(1, n * m, 1, v);
    }

    void update(int pos, int val)
    {
        update(1, n * m, 1, pos, val);
    }

    int search(int value)
    {
        return search(1, n * m, 1, value);
    }
};

SegmentTreeLazy treeRect;
SegmentTreeLazy treeLineRow;
SegmentTreeLazy treeLineCol;
SegmentTreeMinMax treeRow, treeCol;
std::vector <int> t[MAXN];
std::vector <int> r, c;

std::set <std::pair <int,int>> set;
void addL(int row, int col)
{
    if (row > n || col > m || row == 1 || col == 1 || set.count({row, col}))
    {
        return;
    }

    set.insert({row, col});
    std::vector <int> vals;
    vals.push_back(t[row][col]);
    vals.push_back(t[row - 1][col]);
    vals.push_back(t[row][col - 1]);
    vals.push_back(t[row - 1][col - 1]);
    std::sort(vals.begin(), vals.end());
    std::cout << "addL: " << row << ' ' << col << ": " << vals[2] << ' ' << vals[3] - 1 << '\n' << std::flush;
    treeRect.update(vals[2], vals[3] - 1, 1);
}

void remL(int row, int col)
{
    // std::cout << "remL: " << row << ' ' << col << '\n' << std::flush;
    if (row > n || col > m || row == 1 || col == 1 || set.count({row, col}))
    {
        return;
    }

    set.insert({row, col});
    std::vector <int> vals;
    vals.push_back(t[row][col]);
    vals.push_back(t[row - 1][col]);
    vals.push_back(t[row][col - 1]);
    vals.push_back(t[row - 1][col - 1]);
    std::sort(vals.begin(), vals.end());
    std::cout << "remL: " << row << ' ' << col << ": " << vals[2] << ' ' << vals[3] - 1 << '\n' << std::flush;
    treeRect.update(vals[2], vals[3] - 1, -1);
}

void addSingularUp(int row, int col)
{
    int min = std::min(t[row][col], t[row - 1][col]);
    int max = std::max(t[row][col], t[row - 1][col]);
    treeLineCol.update(min, max - 1, 1);

    min = std::min(t[row][col], t[row][col - 1]);
    max = std::max(t[row][col], t[row][col - 1]);
    treeLineRow.update(min, max - 1, 1);
}

void addSingularRect(int row, int col)
{
    std::vector <int> v;
    v.push_back(t[row - 1][col]);
    v.push_back(t[row][col - 1]);
    v.push_back(t[row + 1][col]);
    v.push_back(t[row][col + 1]);
    std::sort(v.begin(), v.end());
    if (t[row][col] < v[1])
    {
        treeRect.update(t[row][col], v[1] - 1, 1);
    }
}

void remSingularRect(int row, int col)
{
    std::vector <int> v;
    v.push_back(t[row - 1][col]);
    v.push_back(t[row][col - 1]);
    v.push_back(t[row + 1][col]);
    v.push_back(t[row][col + 1]);
    std::sort(v.begin(), v.end());
    if (t[row][col] < v[1])
    {
        treeRect.update(t[row][col], v[1] - 1, -1);
    }
}

void addSingular(int row, int col)
{
    int min = std::min(t[row][col], t[row - 1][col]);
    int max = std::max(t[row][col], t[row - 1][col]);
    treeLineCol.update(min, max - 1, 1);

    min = std::min(t[row][col], t[row][col - 1]);
    max = std::max(t[row][col], t[row][col - 1]);
    treeLineRow.update(min, max - 1, 1);

    min = std::min(t[row][col], t[row + 1][col]);
    max = std::max(t[row][col], t[row + 1][col]);
    treeLineCol.update(min, max - 1, 1);

    min = std::min(t[row][col], t[row][col + 1]);
    max = std::max(t[row][col], t[row][col + 1]);
    treeLineRow.update(min, max - 1, 1);
}

void remSingular(int row, int col)
{
    int min = std::min(t[row][col], t[row - 1][col]);
    int max = std::max(t[row][col], t[row - 1][col]);
    treeLineCol.update(min, max - 1, -1);

    min = std::min(t[row][col], t[row][col - 1]);
    max = std::max(t[row][col], t[row][col - 1]);
    treeLineRow.update(min, max - 1, -1);

    min = std::min(t[row][col], t[row + 1][col]);
    max = std::max(t[row][col], t[row + 1][col]);
    treeLineCol.update(min, max - 1, -1);

    min = std::min(t[row][col], t[row][col + 1]);
    max = std::max(t[row][col], t[row][col + 1]);
    treeLineRow.update(min, max - 1, -1);
}

void add(int row, int col)
{
    addL(row, col);
    addL(row + 1, col);
    addL(row, col + 1);
    addL(row + 1, col + 1);
    addSingular(row, col);
    addSingularRect(row, col);
}

void rem(int row, int col)
{
    remL(row, col);
    remL(row + 1, col);
    remL(row, col + 1);
    remL(row + 1, col + 1);
    remSingular(row, col);
    remSingularRect(row, col);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    n = H;
    m = W;
    for (int i = 0 ; i <= n + 1 ; ++i)
    {
        t[i].resize(m + 2, n * m + 1);
    }

    C.insert(C.begin(), -1);
    R.insert(R.begin(), -1);
    for (int &val : R) val++;
    for (int &val : C) val++;

    r = R; c = C;
    treeRow.build(r);
    treeCol.build(c);
    for (int i = 1 ; i <= n * m ; ++i)
    {
        t[R[i]][C[i]] = i;
    }

    treeRect.build();
    treeLineRow.build();
    treeLineCol.build();
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            addL(i, j);
            addSingularUp(i, j);
            addSingularRect(i, j);
        }
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        int min = t[n][i];
        int max = n * m + 1;
        treeLineCol.update(min, max - 1, 1);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        int min = t[i][m];
        int max = n * m + 1;
        treeLineRow.update(min, max - 1, 1);
    }
}

int swap_seats(int a, int b) 
{
    a++; b++;
    int rowA = r[a];
    int colA = c[a];
    int rowB = r[b];
    int colB = c[b];
    set.clear();
    rem(rowA, colA);
    rem(rowB, colB);

    std::swap(t[rowA][colA], t[rowB][colB]);
    std::swap(c[a], c[b]);
    std::swap(r[a], r[b]);
    treeRow.update(a, r[a]);
    treeRow.update(b, r[b]);
    treeCol.update(a, c[a]);
    treeCol.update(b, c[b]);

    set.clear();
    add(rowA, colA);
    add(rowB, colB);

    int ans = 1;
    int pos = 1;
    if (r[1] == r[2])
    {
        pos = treeRow.search(r[1]);
        ans = treeLineRow.query(1, pos, 2);
    }

    if (c[1] == c[2])
    {
        pos = treeCol.search(c[1]);
        ans = treeLineCol.query(1, pos, 2);
    }

    std::cout << "ans before: " << ans << '\n';
    if (pos < n * m)
    {
        ans += treeRect.query(pos + 1, n * m, 0);
    }

    return ans;
}

Compilation message (stderr)

seats.cpp: In member function 'void SegmentTreeLazy::build(int, int, int)':
seats.cpp:47:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'void SegmentTreeLazy::update(int, int, int, int, int, int)':
seats.cpp:85:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'SegmentTreeLazy::Node SegmentTreeLazy::query(int, int, int, int, int)':
seats.cpp:100:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'void SegmentTreeMinMax::build(int, int, int, std::vector<int>&)':
seats.cpp:159:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  159 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'void SegmentTreeMinMax::update(int, int, int, int, int)':
seats.cpp:173:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  173 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'int SegmentTreeMinMax::search(int, int, int, int)':
seats.cpp:187:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  187 |         int mid = l + r >> 1;
      |                   ~~^~~

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