Submission #796811

#	Time	Username	Problem	Language	Result	Execution time	Memory
796811		fatemetmhr	Seats (IOI18_seats)	C++17	100 / 100	2082 ms	173876 KiB

seats

// Be name khode //

#include "seats.h"
#include <bits/stdc++.h>
 
using namespace std;


 
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair
 
typedef long long ll;
 
const int maxn = 1e6 + 5;
const int maxnt = 4e6 + 30;
const int lg    = 20;

std::vector<int> r;

int n, m, have = 0, sgn, av[5];
pair <int, int> a[maxn];
vector <int> ind[maxn], st[maxn];
vector <pair<int, int>> adj = {{0, 0}, {-1, 0}, {0, -1}, {-1, -1}};
vector <pair<int, int>> sq = {{0, 0}, {1, 0}, {0, 1}, {1, 1}};

namespace seg{

    int lazy[maxnt];
    pair <int, int> mn[maxnt];

    void upd(int l, int r, int lq, int rq, int val, int v){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            lazy[v] += val;
            mn[v].fi += val;
            return;
        }
        int mid = (l + r) >> 1;
        upd(l, mid, lq, rq, val, v * 2);
        upd(mid, r, lq, rq, val, v * 2 + 1);
        mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
        if(mn[v * 2].fi == mn[v * 2 + 1].fi)
            mn[v].se = mn[v * 2].se + mn[v * 2 + 1].se;
        mn[v].fi += lazy[v];
    }

    void build(int l, int r, int v){
        mn[v].se = r - l;
        if(r - l == 1)
            return;
        int mid = (l + r) >> 1;
        build(l, mid, v * 2);
        build(mid, r, v * 2 + 1);
    }
}

bool ok(int x, int y){
    return min(x, y) >= 0 && x + 1 < n && y + 1 < m;
}

void upd(int x, int y, int val){
    if(st[x][y] == val)
        return;
    st[x][y] = val;
    int pt = 0;
    for(auto [u, v] : sq){
        //cout << x << ' ' << y << ' ' << u << ' ' << v << ' ' << x 
        int w = ind[x + u][y + v];
        av[pt++] = w;
        //cout << "ha? " << x << ' ' << y << ' ' << u << ' ' << v << ' ' << w << endl;
    }
    sort(av, av + pt);
    //cout << "upd of " << x << ' ' << y << ' ' << val << endl;
    seg::upd(0, sgn, av[0], av[1], val, 1);
    seg::upd(0, sgn, av[2], av[3], val, 1);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H;
    m = W;
    sgn = n * m;
    seg::build(0, sgn, 1);
    for(int i = 0; i < n + 2; i++){
        ind[i].resize(m + 2);
        st[i].resize(m + 2, -1);
        for(int j = 0; j < m + 2; j++)
            ind[i][j] = n * m;
    }
    for(int i = 0; i < n * m; i++){
        a[i] = {R[i] + 1, C[i] + 1}; 
        ind[R[i] + 1][C[i] + 1] = i;
    }
    n += 2;
    m += 2;
    for(int i = 0; i < n - 1; i++)
        for(int j = 0; j < m - 1; j++)
            upd(i, j, 1);
}


int swap_seats(int x, int y) {
    for(auto [u, v] : adj){
        if(ok(a[x].fi + u, a[x].se + v))
            upd(a[x].fi + u, a[x].se + v, -1);
        if(ok(a[y].fi + u, a[y].se + v))
            upd(a[y].fi + u, a[y].se + v, -1);
    }
    swap(a[x], a[y]);
    ind[a[x].fi][a[x].se] = x;
    ind[a[y].fi][a[y].se] = y;
    for(auto [u, v] : adj){
        if(ok(a[x].fi + u, a[x].se + v))
            upd(a[x].fi + u, a[x].se + v, 1);
        if(ok(a[y].fi + u, a[y].se + v))
            upd(a[y].fi + u, a[y].se + v, 1);
    }
    assert(seg::mn[1].fi >= 4);
    //cout << "now " << x << ' ' << y << ' ' << seg::mn[1].fi << ' ' << seg::mn[1].se << endl;
    return seg::mn[1].se;
}

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