Submission #1010994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010994		boris_mihov	Seats (IOI18_seats)	C++17	100 / 100	2867 ms	230588 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 SegmentTree
{
    struct Node
    {
        std::pair <int,int> min;
        std::pair <int,int> lazy;
        int cnt;
        
        Node()
        {
            min = lazy = {0, 0};
            cnt = 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, 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 == std::make_pair(0, 0))
        {
            return;
        }

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

        tree[node].lazy = {0, 0};
    }

    void update(int l, int r, int node, int queryL, int queryR, std::pair <int,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];
    }

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

    void update(int l, int r, int val, int val2)
    {
        if (l > r) return;
        update(1, n * m, 1, l, r, {val, val2});
    }

    int query()
    {
        return tree[1].cnt;
    }
};

SegmentTree tree;
std::vector <int> t[MAXN];
std::vector <int> r, c;
std::set <std::pair <int,int>> used;

void addL(int row, int col)
{
    if (used.count({row, col}))
    {
        return;
    }

    used.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());
    tree.update(vals[0], vals[1] - 1, 1, 0);
    tree.update(vals[2], vals[3] - 1, 0, 1);
}

void remL(int row, int col)
{
    // std::cout << "remL: " << row << ' ' << col << '\n' << std::flush;
    if (used.count({row, col}))
    {
        return;
    }

    used.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());
    tree.update(vals[0], vals[1] - 1, -1, 0);
    tree.update(vals[2], vals[3] - 1, 0, -1);
}

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

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

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;
    for (int i = 1 ; i <= n * m ; ++i)
    {
        t[R[i]][C[i]] = i;
    }
    
    tree.build();
    for (int i = 1 ; i <= n + 1 ; ++i)
    {
        for (int j = 1 ; j <= m + 1 ; ++j)
        {
            addL(i, j);
        }
    }

    tree.query();
}

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];
    used.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]);

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

    return tree.query();
}

Compilation message (stderr)

seats.cpp: In member function 'void SegmentTree::build(int, int, int)':
seats.cpp:48:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, std::pair<int, int>)':
seats.cpp:89:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         int mid = l + r >> 1;
      |                   ~~^~~

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