Submission #900410

#	Time	Username	Problem	Language	Result	Execution time	Memory
900410		12345678	Seats (IOI18_seats)	C++17	100 / 100	1219 ms	115252 KiB

seats

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

using namespace std;

const int nx=1e6+5;
int N, h, w, r[nx], c[nx], dp[nx], tmp[5][5], mp[5][5], dx[]={-1, -1, -1, 0, 0, 0, 1, 1, 1}, dy[]={-1, 0, 1, -1, 0, 1, -1, 0, 1};
vector<vector<int>> v;

struct segtree
{
    struct node
    {
        int mn, f, lz;
    } d[4*nx];
    node merge(node a, node b)
    {
        if (a.mn==b.mn) a.f+=b.f;
        if (a.mn<=b.mn) return a;
        else return b;
    }
    void pushlz(int l, int r, int i)
    {
        if (l==r) return d[i].mn+=d[i].lz, d[i].lz=0, void();
        d[2*i].lz+=d[i].lz;
        d[2*i+1].lz+=d[i].lz;
        d[i].mn+=d[i].lz;
        d[i].lz=0;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i].f=1);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return d[i].lz=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
} s;

int solve()
{
    int cnt=0;
    for (int i=0; i<5; i++) for (int j=0; j<5; j++) tmp[i][j]=0;
    for (int i=1; i<=4; i++) for (int j=1; j<=3; j++) if (mp[i][j]+mp[i-1][j]==1) tmp[i][j]=1;
    for (int i=1; i<=4; i++) for (int j=1; j<=3; j++) cnt+=(tmp[i][j]&&(!tmp[i][j-1]));
    for (int i=0; i<5; i++) for (int j=0; j<5; j++) tmp[i][j]=0;
    for (int i=1; i<=3; i++) for (int j=1; j<=4; j++) if (mp[i][j]+mp[i][j-1]==1) tmp[i][j]=1;
    for (int i=1; i<=3; i++) for (int j=1; j<=4; j++) cnt+=(tmp[i][j]&&(!tmp[i-1][j]));
    return cnt;
}

void precompute()
{
    for (int i=0; i<(1<<9); i++)
    {
        if (i&(1<<4)) continue;
        for (int j=0; j<9; j++) mp[j/3+1][(j%3)+1]=(i&(1<<j))>0;
        dp[i]=-solve();
        mp[2][2]=1;
        dp[i]+=solve();
    }
}

void updateseats(int x, int y, int mul)
{
    if (x==0||x==h+1||y==0||y==w+1) return;
    int c=0;
    for (int i=0; i<9; i++) if (i!=4&&v[x+dx[i]][y+dy[i]]<v[x][y]) c|=(1<<i);
    s.update(1, N, 1, v[x][y], N, mul*dp[c]);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h=H; w=W; N=h*w;
    v.resize(h+2);
    for (int i=0; i<h+2; i++) v[i].resize(w+2);
    for (int i=0; i<h+2; i++) for (int j=0; j<w+2; j++) v[i][j]=1e9;
    for (int i=1; i<=N; i++) r[i]=R[i-1]+1;
    for (int i=1; i<=N; i++) c[i]=C[i-1]+1;
    for (int i=1; i<=N; i++) v[r[i]][c[i]]=i;
    s.build(1, N, 1);
    precompute();
    for (int i=1; i<=N; i++) updateseats(r[i], c[i], 1);
}

int swap_seats(int a, int b) {
    a++; b++;
    set<pair<int, int>> upd;
    for (int i=-1; i<=1; i++) for (int j=-1; j<=1; j++) upd.insert({r[a]+i, c[a]+j}), upd.insert({r[b]+i, c[b]+j});
    for (auto [x, y]:upd) updateseats(x, y, -1);
    swap(v[r[a]][c[a]], v[r[b]][c[b]]);
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    for (auto [x, y]:upd) updateseats(x, y, 1);
    return s.d[1].f;
}

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