Submission #1262880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262880		phoenix0423	Seats (IOI18_seats)	C++20	0 / 100	2306 ms	112768 KiB

seats

#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
// #define int long long 
#define lowbit(x) x&-x
#define ckmax(a, b) a = max(a, b)
const int maxn = 1e6 + 5;
const int N = 998244353;
const int INF = 1e9;
vector<vector<int>> g;
int r[maxn], c[maxn];
int n, m, nm;

pll st[maxn * 4];
int tag[maxn * 4];

void build(int v = 1, int l = 0, int r = nm - 1){
    st[v] = {0, r - l + 1};
    if(l == r) return;
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
}
void cast(int v, int val){
    tag[v] += val, st[v].f += val;
}

void push(int v){
    if(tag[v]){
        cast(v * 2, tag[v]);
        cast(v * 2 + 1, tag[v]);
        tag[v] = 0;
    }
}
pll op(pll a, pll b){
    if(a.f != b.f) return a.f < b.f ? a : b;
    return {a.f, a.s + b.s};
}

void upd(int l, int r, int val, int v = 1, int L = 0, int R = nm - 1){
    if(v == 1) cout<<"upd : "<<l<<" "<<r<<" "<<val<<"\n";
    if(l > R || r < L) return;
    if(l <= L && r >= R){
        cast(v, val);
        return;
    }
    push(v);
    int m = (L + R) / 2;
    upd(l, r, val, v * 2, L, m);
    upd(l, r, val, v * 2 + 1, m + 1, R);
    st[v] = op(st[v * 2], st[v * 2 + 1]);
}

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool inbound(int x, int y){ return x >= 0 && y >= 0 && x <= n + 1 && y <= m + 1;}

void chg(int i, int j, int val){
    int mn = INF;
    for(int d = 0; d < 4; d++){
        int x = i + dx[d], y = j + dy[d];
        if(!inbound(x, y)) continue;
        mn = min(mn, g[x][y]);
    }
    if(mn > g[i][j] && g[i][j]) upd(g[i][j], mn - 1, val);
}

void box(int i, int j, int val){
    vector<int> c({g[i - 1][j - 1], g[i - 1][j], g[i][j - 1], g[i][j]});
    sort(c.begin(), c.end());
    upd(c[0], c[1] - 1, val);
    upd(c[2], c[3] - 1, val);
}

void give_initial_chart(int n, int m, vector<int> R, vector<int> C){
    g = vector<vector<int>>(n + 2, vector<int>(m + 2, n * m + 1));
    ::n = n, ::m = m, nm = n * m;
    build();
    for(int i = 0; i < n * m; i++) r[i] = ++R[i], c[i] = ++C[i], g[r[i]][c[i]] = i;
    for(int i = 1; i <= n + 1; i++){
        for(int j = 1; j <= m + 1; j++){
            box(i, j, 1);
        }
    }
}

void get(int x, int y, vector<pll> &a){
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            if(inbound(x + i, y + j) && x + i && y + j) a.pb({x + i, y + j});
        }
    }
    a.pb({x, y});
}
void sort_unique(vector<pll> &a){
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
}
ostream &operator<<(ostream &s, pll &p){
    s << "["<<p.f<<", "<<p.s<<"] ";
    return s;
}

int swap_seats(int a, int b){
    int x1 = r[a], y1 = c[a], x2 = r[b], y2 = c[b];
    vector<pll> pt, pt2;
    get(x1, y1, pt), get(x2, y2, pt);
    sort_unique(pt);
    for(auto [x, y] : pt) box(x, y, -1);
    r[a] = x2, c[a] = y2, r[b] = x1, c[b] = y1;
    swap(g[x1][y1], g[x2][y2]);
    for(auto [x, y] : pt) box(x, y, 1);
    if(st[1].f > 4) return 0;
    return st[1].s;
}

// signed main(void){
//     fastio;
// }

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