Submission #461403

#	Time	Username	Problem	Language	Result	Execution time	Memory
461403		SHZhang	Seats (IOI18_seats)	C++14	100 / 100	3645 ms	176704 KiB

seats

#include "seats.h"
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int h, w;
int x[1000005], y[1000005];
int* grid[1000005];

int delta[1000005];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

struct Segtree {
    int l, r;
    Segtree* lchild;
    Segtree* rchild;
    int minv, freq, lazy;
};

Segtree* build(int l, int r)
{
    Segtree* st = new Segtree;
    st->l = l; st->r = r;
    st->minv = 0; st->freq = 1; st->lazy = 0;
    if (l == r) {
        st->lchild = st->rchild = NULL;
    } else {
        st->lchild = build(l, (l + r) / 2);
        st->rchild = build((l + r) / 2 + 1, r);
    }
    return st;
}

void pushdown(Segtree* st)
{
    int val = st->lazy;
    st->minv += val;
    st->lazy = 0;
    if (st->l == st->r) return;
    st->lchild->lazy += val;
    st->rchild->lazy += val;
}

void modify(Segtree* st, int l, int r, int change)
{
    pushdown(st);
    if (st->r < l || r < st->l) return;
    if (l <= st->l && st->r <= r) {
        st->lazy += change;
        pushdown(st);
    } else {
        modify(st->lchild, l, r, change);
        modify(st->rchild, l, r, change);
        st->minv = min(st->lchild->minv, st->rchild->minv);
        if (st->lchild->minv == st->rchild->minv) {
            st->freq = st->lchild->freq + st->rchild->freq;
        } else if (st->lchild->minv < st->rchild->minv) {
            st->freq = st->lchild->freq;
        } else {
            st->freq = st->rchild->freq;
        }
    }
}

Segtree* root;

int get_time_weight(int r, int c, int t)
{
    //fprintf(stderr, "! %d %d %d\n", r, c, t);
    if (grid[r][c] > t) {
        int hcnt = 0;
        for (int d = 0; d < 4; d++) {
            if (r + dx[d] >= 0 && c + dy[d] >= 0 && grid[r + dx[d]][c + dy[d]] <= t) hcnt++;
        }
        return hcnt >= 2 ? 1 : 0;
    } else {
        int ccnt = 0;
        for (int d = 0; d < 4; d++) {
            //printf("! %d %d %d\n", r + dx[d], c + dy[d], (r + dx[d] < 0 || c + dy[d] < 0 || grid[r + dx[d]][c + dy[d]] > t));
            if (r + dx[d] < 0 || c + dy[d] < 0 || grid[r + dx[d]][c + dy[d]] > t) {
                int d2 = (d + 1) % 4;
                if (r + dx[d2] < 0 || c + dy[d2] < 0 || grid[r + dx[d2]][c + dy[d2]] > t) ccnt++;
            }
        }
        //printf("!! %d\n", lcnt);
        return ccnt;
    }
}

int get_delta(int r, int c)
{
    int diff = get_time_weight(r, c, grid[r][c]) - get_time_weight(r, c, grid[r][c] - 1);
    for (int d = 0; d < 4; d++) {
        int r2 = r + dx[d];
        int c2 = c + dy[d];
        if (r2 < 0 || r2 >= h || c2 < 0 || c2 >= w) continue;
        diff += get_time_weight(r2, c2, grid[r][c]);
        diff -= get_time_weight(r2, c2, grid[r][c] - 1);
    }
    return diff;
}

void update_delta(int r, int c)
{
    //fprintf(stderr, "! %d %d\n", r, c);
    if (r < 0 || r >= h || c < 0 || c >= w) return;
    int id = grid[r][c];
    int old_delta = delta[id];
    delta[id] = get_delta(r, c);
    //fprintf(stderr, "! %d %d\n", r, c);
    modify(root, id, h * w - 1, delta[id] - old_delta);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h = H; w = W;
    root = build(0, h * w - 1);
    for (int i = 0; i <= h; i++) {
        grid[i] = new int[w + 1];
    }
    for (int i = 0; i <= h; i++) {
        for (int j = 0; j <= w; j++) {
            grid[i][j] = h * w;
        }
    }
    for (int i = 0; i < h * w; i++) {
        x[i] = R[i]; y[i] = C[i];
        grid[x[i]][y[i]] = i;
        //printf("! %d %d %d\n", x[i], y[i], i);
    }
    //fprintf(stderr, "! %d %d %d\n", grid[0][0], get_time_weight(1, 0, 0), get_time_weight(1, 0, 1));
    for (int i = 0; i < h * w; i++) {
        update_delta(x[i], y[i]);
        //fprintf(stderr, "%d ", delta[i]);
    }
    //fprintf(stderr, "\n");
}

int swap_seats(int a, int b) {
    int x1 = x[a];
    int y1 = y[a];
    int x2 = x[b];
    int y2 = y[b];
    swap(grid[x1][y1], grid[x2][y2]);
    x[a] = x2; y[a] = y2;
    x[b] = x1; y[b] = y1;
    for (int d1 = -2; d1 <= 2; d1++) {
        for (int d2 = -2; d2 <= 2; d2++) {
            if (max(d1, -d1) + max(d2, -d2) > 2) continue;
            update_delta(x1 + d1, y1 + d2);
            update_delta(x2 + d1, y2 + d2);
        }
    }
    //fprintf(stderr, "! %d %d\n", get_time_weight(1, 1, 1), get_time_weight(1, 1, 2));
    /*for (int i = 0; i < h * w; i++) {
        fprintf(stderr, "%d ", delta[i]);
    }*/
    //fprintf(stderr, "\n");
    return root->freq;
}

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