Submission #1080671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080671		asdasdqwer	Seats (IOI18_seats)	C++14	37 / 100	4005 ms	72788 KiB

seats

// #pragma GCC optimize("O3")
// #pragma GCC target("avx,avx2,sse4")

#include "seats.h"

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

struct MaxSegtree {
    vector<int> seg;int n;
    void init(int sz, vector<int> &a) {
        n=1;
        while (n<sz) n*=2;
        seg.assign(2*n, -1);
        build(a, 0, 0, n);
    }

    void combine(int x) {
        seg[x]=max(seg[2*x+1], seg[2*x+2]);
    }

    void build(vector<int> &a, int x, int lx, int rx) {
        if (rx-lx==1) {
            if (lx < (int)a.size()) {
                seg[x] = a[lx];
            }

            return;
        }

        int m=(lx+rx)/2;
        build(a, 2*x+1, lx, m);
        build(a, 2*x+2, m, rx);

        combine(x);
    }

    void st(int i, int v, int x, int lx, int rx) {
        if (rx-lx==1) {
            seg[x]=v;
            return;
        }

        int m=(lx+rx)/2;
        if (i<m) st(i,v,2*x+1,lx,m);
        else st(i,v,2*x+2,m,rx);
        combine(x);
    }

    void st(int i, int v) {
        st(i,v,0,0,n);
    }

    int walk(int v, int x, int lx, int rx) {
        while (rx-lx!=1) {
            int m=(lx+rx)/2;
            if (seg[2*x+1] > v) {x=2*x+1;rx=m;}
            else {x=2*x+2;lx=m;}
        }
        return lx;
    }

    int walk(int v) {
        if (seg[0] <= v) return 1e9;
        return walk(v,0,0,n);
    }
};


struct MinSegtree {
    vector<int> seg;int n;
    void init(int sz, vector<int> &a) {
        n=1;
        while (n<sz) n*=2;
        seg.assign(2*n, 1e9);
        build(a, 0, 0, n);
    }

    void combine(int x) {
        seg[x]=min(seg[2*x+1], seg[2*x+2]);
    }

    void build(vector<int> &a, int x, int lx, int rx) {
        if (rx-lx==1) {
            if (lx < (int)a.size()) {
                seg[x] = a[lx];
            }

            return;
        }

        int m=(lx+rx)/2;
        build(a, 2*x+1, lx, m);
        build(a, 2*x+2, m, rx);

        combine(x);
    }

    void st(int i, int v, int x, int lx, int rx) {
        if (rx-lx==1) {
            seg[x]=v;
            return;
        }

        int m=(lx+rx)/2;
        if (i<m) st(i,v,2*x+1,lx,m);
        else st(i,v,2*x+2,m,rx);
        combine(x);
    }

    void st(int i, int v) {
        st(i,v,0,0,n);
    }

    int walk(int v, int x, int lx, int rx) {
        while (rx-lx!=1) {
            int m=(lx+rx)/2;
            if (seg[2*x+1] < v) {x=2*x+1;rx=m;}
            else {x=2*x+2;lx=m;}
        }
        return lx;
    }

    int walk(int v) {
        if (seg[0] >= v) return 1e9;
        return walk(v,0,0,n);
    }
};

MinSegtree mnx, mny;
MaxSegtree mxx, mxy;

vector<int> r, c;
int h,w;

vector<array<int,4>> vals;
vector<bool> rect;
int cnt_rects=1;
bool noseg = false;

void before(int i) {
    vals[i] = vals[i-1];
    vals[i][0] = min(vals[i][0], r[i]);
    vals[i][1] = max(vals[i][1], r[i]);
    vals[i][2] = min(vals[i][2], c[i]);
    vals[i][3] = max(vals[i][3], c[i]);

    if ((vals[i][1]-vals[i][0]+1) * (vals[i][3]-vals[i][2]+1) == i+1) rect[i]=true;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    int n=H*W;
    h=H-1;
    w=W-1;
    r = R;c=C;
    if (n <= 10000 || H > 1000 || W > 1000) {
        noseg = true;
        vals.assign(n, {0,0,0,0});
        rect.assign(n,false);
        vals[0] = {r[0], r[0], c[0], c[0]};
        rect[0] = true;
        for (int i=1;i<n;i++) {
            before(i);
            if (rect[i])cnt_rects++;
        }
        return;
    }
    mnx.init(n,r);mxx.init(n,r);
    mny.init(n,c);mxy.init(n,c);
}


int seg(int a, int b) {
    // swap everything for a and b
    swap(r[a],r[b]);
    swap(c[a],c[b]);

    mnx.st(a, r[a]);
    mxx.st(a, r[a]);
    mny.st(a, c[a]);
    mxy.st(a, c[a]);

    mnx.st(b, r[b]);
    mxx.st(b, r[b]);
    mny.st(b, c[b]);
    mxy.st(b, c[b]);

    // recalculate number of rectangles

    int cnt=0;

    int sX = r[0], eX = r[0], sY = c[0], eY = c[0];
    while (sX != 0 || eX != h || sY != 0 || eY != w) {
        // calculate minimum excluded element
        vector<int> vv = {mnx.walk(sX), mxx.walk(eX), mny.walk(sY), mxy.walk(eY)};
        int mn=1e9;
        for (auto &x:vv) mn=min(mn,x);
        if (mn == (eX-sX+1)*(eY-sY+1)) cnt++;

        sX = min(sX, r[mn]);
        sY = min(sY, c[mn]);
        eX = max(eX, r[mn]);
        eY = max(eY, c[mn]);
    }

    return cnt+1;
}

int swap_seats(int a, int b) {
    if (!noseg) return seg(a,b);
    if (a > b) swap(a,b);
    
    swap(r[a],r[b]);
    swap(c[a],c[b]);

    if (a == 0) {
        vals[0] = vals[0] = {r[0], r[0], c[0], c[0]};
        a++;
    }

    for (int i=a;i<=b;i++) {
        if (rect[i]) {
            cnt_rects--;
            rect[i]=false;
        }
        before(i);
        if (rect[i]) cnt_rects++;
    }
    return cnt_rects;
}

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