Submission #235233

#	Time	Username	Problem	Language	Result	Execution time	Memory
235233		lyc	Seats (IOI18_seats)	C++14	100 / 100	3890 ms	173040 KiB

seats

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

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
using ii=pair<int,int>;

vector<vector<int>> g;
vector<int> R, C;

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

struct node {
    int s, e, mn, cnt, lazy;
    node *l, *r;
    node(int s, int e): s(s), e(e), mn(0), cnt(e-s+1), lazy(0) {
        if (s != e) {
            int m = (s+e)/2;
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
    void prop() {
        if (lazy == 0) return;
        if (s != e) {
            l->lazy += lazy;
            r->lazy += lazy;
        }
        mn += lazy;
        lazy = 0;
    }
    void update(int x, int y, int v) {
        if (x > y) return;
        prop();
        int m = (s+e)/2;
        if (s == x && e == y) { lazy += v; return; }
        else if (y <= m) l->update(x,y,v);
        else if (x > m) r->update(x,y,v);
        else l->update(x,m,v), r->update(m+1,y,v);
        l->prop(), r->prop();
        mn = min(l->mn, r->mn);
        cnt = 0;
        if (l->mn == mn) cnt += l->cnt;
        if (r->mn == mn) cnt += r->cnt;
    }
} *root;

void add(int i, int j, int val) {
    int v[4] = {0}, mn = H*W;
    FOR(k,0,3){
        int x = i+dx[k], y = j+dy[k];
        if (x >= 0 and x < H && y >= 0 and y < W) v[k] = g[x][y];
        else v[k] = H*W;
        if (k < 2) mn = min(mn,v[k]);
    }
    sort(v,v+4);
    int c = g[i][j];
    //TRACE(c _ mn-1 _ "|" _ v[1] _ c-1 _ "|" _ val);
    root->update(c,mn-1,val);
    root->update(v[1],c-1,val);
}

void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C) {
    H = _H, W = _W;
    R = _R, C = _C;
    FOR(i,0,H-1){ g.push_back(vector<int>(W)); }
    FOR(i,0,SZ(R)-1){ g[R[i]][C[i]] = i; }

    root = new node(0,H*W-1);
    FOR(i,0,H-1){
        FOR(j,0,W-1){
            add(i,j,1);
        }
    }
    //TRACE(root->mn _ root->cnt);
}

int swap_seats(int a, int b) {
    vector<ii> pts;
    //TRACE(R[a] _ C[a] _ R[b] _ C[b]);
    FOR(i,0,4){
        int x = R[a]+dx[i], y = C[a]+dy[i];
        if (x >= 0 and x < H && y >= 0 and y < W) pts.emplace_back(x,y);
    }
    FOR(i,0,4){
        int x = R[b]+dx[i], y = C[b]+dy[i];
        if (x >= 0 and x < H && y >= 0 and y < W) pts.emplace_back(x,y);
    }
    sort(ALL(pts));
    pts.resize(unique(ALL(pts))-pts.begin());
    for (ii x : pts) {
        add(x.first,x.second,-1);
    }
    swap(g[R[a]][C[a]],g[R[b]][C[b]]);
    swap(R[a],R[b]);
    swap(C[a],C[b]);
    for (ii x : pts) {
        add(x.first,x.second,1);
    }
    root->prop();
    return (root->mn == 1 ? root->cnt : 0);
}

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