Submission #745200

#	Time	Username	Problem	Language	Result	Execution time	Memory
745200		danikoynov	Seats (IOI18_seats)	C++14	100 / 100	3257 ms	134284 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10;

struct node
{
    int mx, cnt;

    node()
    {
        mx = 1e9;
        cnt = 0;
    }
};

node merge_node(node lf, node rf)
{
    node nd;
    nd.mx = min(lf.mx, rf.mx);
    nd.cnt = 0;
    if (lf.mx == nd.mx)
        nd.cnt += lf.cnt;
    if (rf.mx == nd.mx)
        nd.cnt += rf.cnt;
    return nd;
}

node tree[4 * maxn];
int lazy[4 * maxn];
void push_lazy(int root, int left, int right)
{
    tree[root].mx += lazy[root];
    if (left != right)
    {
        lazy[root * 2] += lazy[root];
        lazy[root * 2 + 1] += lazy[root];
    }
    lazy[root] = 0;
}
void build(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].cnt = 1;
        return;
    }

    int mid = (left + right) / 2;
    build(root * 2, left, mid);
    build(root * 2 + 1, mid + 1, right);
}


void update_range(int root, int left, int right, int qleft, int qright, int val)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
    return;

    if (left >= qleft && right <= qright)
    {
        lazy[root] = val;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    update_range(root * 2, left, mid, qleft, qright, val);
    update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

int h, w, n;
vector < vector < int > > val;

void change(int x, int y, int k)
{
    vector < int > cur;
    cur.push_back(val[x][y]);
    cur.push_back(val[x][y + 1]);
    cur.push_back(val[x + 1][y]);
    cur.push_back(val[x + 1][y + 1]);
    ///cout << "change " << x << " " << y << " " << k << endl;

    sort(cur.begin(), cur.end());
    update_range(1, 0, n - 1, cur[0], cur[1] - 1, k);
    update_range(1, 0, n - 1, cur[2], cur[3] - 1, k);
    //cout << cur[0] << " " << cur[1] - 1 << endl;
    //cout << cur[2] << " " << cur[3] - 1 << endl;
}

void action_cell(int x, int y, int k)
{
    for (int dx = -1; dx <= 0; dx ++)
        for (int dy = -1; dy <= 0; dy ++)
    {
        change(x + dx, y + dy, k);
    }
}
vector < int > r, c;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
    h = H;
    w = W;
    n = h * w;
    build(1, 0, n - 1);
    val.resize(h + 2, vector < int > (w + 2, n));
        for (int i = 0; i < n; i ++)
        {
            val[R[i] + 1][C[i] + 1] = i;
            r.push_back(R[i] + 1);
            c.push_back(C[i] + 1);
        }

    for (int i = 0; i <= h; i ++)
        for (int j = 0; j <= w; j ++)
            change(i, j, 1);

            //cout << tree[1].cnt << endl;
        //exit(0);
}

int swap_seats(int a, int b)
{
    action_cell(r[a], c[a], -1);
    action_cell(r[b], c[b], -1);
    swap(val[r[a]][c[a]], val[r[b]][c[b]]);
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    action_cell(r[a], c[a], +1);
    action_cell(r[b], c[b], +1);
    return tree[1].cnt;
}

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