Submission #185446

#	Time	Username	Problem	Language	Result	Execution time	Memory
185446		Anai	Seats (IOI18_seats)	C++14	0 / 100	1895 ms	60696 KiB

seats

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

#define x first
#define y second
using namespace std;

using pii = pair<int, int>;

const int A = 1e6 + 5;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

struct Nod {
    int min, cnt, lazy;
};


vector<vector<int>> mx;
vector<int> row, col;
int n, m, a;

int ql, qr, qval;

Nod pom[A * 4];


static void prop(int nod) {
    pom[2 * nod + 1].lazy+= pom[nod].lazy;
    pom[2 * nod].lazy+= pom[nod].lazy;
    pom[nod].min+= pom[nod].lazy;
    pom[nod].lazy = 0;
}

static void update(int nod, int st, int dr) {
    if (qr < ql)
        return;
    if (ql <= st && dr <= qr) {
        pom[nod].lazy+= qval;
        return;
    }
    int mid = (st + dr) / 2;
    prop(nod);
    if (ql <= mid)
        update(2 * nod, st, mid);
    if (mid < qr)
        update(2 * nod + 1, mid + 1, dr);
    pom[nod].min = min(pom[2 * nod].min + pom[2 * nod].lazy, pom[2 * nod + 1].min + pom[2 * nod + 1].lazy);
    pom[nod].cnt = (pom[nod].min == pom[2 * nod].min + pom[2 * nod].lazy ? pom[2 * nod].cnt : 0);
    pom[nod].cnt+= (pom[nod].min == pom[2 * nod + 1].min + pom[2 * nod + 1].lazy ? pom[2 * nod + 1].cnt : 0);
}

static pii query(int nod, int st, int dr) {
    if (ql <= st && dr <= qr)
        return pii(pom[nod].min + pom[nod].lazy, pom[nod].cnt);
    int mid = (st + dr) / 2;
    pii ans = {1e9, 1e9};

    prop(nod);
    if (ql <= mid)
        ans = query(2 * nod, st, mid);
    if (mid < qr) {
        pii ret = query(2 * nod + 1, mid + 1, dr);
        if (ret.x < ans.x)
            ans = ret;
        else if (ret.x == ans.x)
            ans.y+= ret.y;
    }

    return ans;
}

static void baga(int idx) {
    vector<pii> nidx;

    if (idx == a)
        return;

    int x = row[idx], y = col[idx];
    for (int dir = 0; dir < 4; ++dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        int val = mx[nx][ny];

        nidx.emplace_back(val, dir);
    }

    sort(begin(nidx), end(nidx));
    ql = idx;
    qr = nidx[0].x - 1;
    qval = 10;
    update(1, 0, a);

    ql = max(idx, nidx[0].x);
    qr = nidx[1].x - 1;
    qval = 2;
    update(1, 0, a);

    if (nidx[0].y % 2 == nidx[1].y % 2)
        return;

    ql = max(idx, nidx[1].x);
    qr = nidx[2].x - 1;
    qval = 1;
    update(1, 0, a);
}

static void scoate(int idx) {
    vector<pii> nidx;

    if (idx == a)
        return;

    int x = row[idx], y = col[idx];
    for (int dir = 0; dir < 4; ++dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        int val = mx[nx][ny];

        nidx.emplace_back(val, dir);
    }

    sort(begin(nidx), end(nidx));
    ql = idx;
    qr = nidx[0].x - 1;
    qval = -10;
    update(1, 0, a);

    ql = max(idx, nidx[0].x);
    qr = nidx[1].x - 1;
    qval = -2;
    update(1, 0, a);

    if (nidx[0].y % 2 == nidx[1].y % 2)
        return;

    ql = max(idx, nidx[1].x);
    qr = nidx[2].x - 1;
    qval = -1;
    update(1, 0, a);
}

static void meh(int nod, int st, int dr) {
    if (st == dr) {
        pom[nod].cnt = 1;
        return;
    }
    int mid = (st + dr) / 2;
    meh(2 * nod, st, mid);
    meh(2 * nod + 1, mid + 1, dr);
    pom[nod].cnt = dr - st + 1;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    swap(row, R);
    swap(col, C);
    n = H;
    m = W;
    a = n * m;

    mx = vector<vector<int>>(n + 5, vector<int>(m + 5));
    for (int i = 0; i < a; ++i)
        mx[++row[i]][++col[i]] = i;

    for (int i = 0; i <= n + 1; ++i)
        mx[i][0] = mx[i][m + 1] = a;
    for (int j = 0; j <= m + 1; ++j)
        mx[0][j] = mx[n + 1][j] = a;

    meh(1, 0, a);
    
    for (int i = 0; i < a; ++i)
        baga(i);
}

int swap_seats(int u, int v) {
    int xu = row[u], yu = col[u];
    int xv = row[v], yv = col[v];

    scoate(u);
    scoate(v);
    for (int dir = 0; dir < 4; ++dir) {
        int nx = xu + dx[dir];
        int ny = yu + dy[dir];
        scoate(mx[nx][ny]);
    }
        
    for (int dir = 0; dir < 4; ++dir) {
        int nx = xv + dx[dir];
        int ny = yv + dy[dir];
        scoate(mx[nx][ny]);
    }

    swap(mx[xu][yu], mx[xv][yv]);
    swap(col[u], col[v]);
    swap(row[u], row[v]);

    baga(u);
    baga(v);
    for (int dir = 0; dir < 4; ++dir) {
        int nx = xu + dx[dir];
        int ny = yu + dy[dir];
        baga(mx[nx][ny]);
    }
        
    for (int dir = 0; dir < 4; ++dir) {
        int nx = xv + dx[dir];
        int ny = yv + dy[dir];
        baga(mx[nx][ny]);
    }

    ql = 1, qr = a - 1;
    return 1 + query(1, 0, a).y;
}

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