Submission #1077461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077461		asdasdqwer	Seats (IOI18_seats)	C++14	31 / 100	4097 ms	73768 KiB

seats

#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 get(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return 1e9;
        if (lx >= l && rx <= r) return seg[x];

        int m=(lx+rx)/2;
        return max(get(l,r,2*x+1,lx,m), get(l,r,2*x+2,m,rx));
    }

    int get(int l, int r) {
        return get(l,r,0,0,n);
    }

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

    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 get(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return 1e9;
        if (lx >= l && rx <= r) return seg[x];

        int m=(lx+rx)/2;
        return min(get(l,r,2*x+1,lx,m), get(l,r,2*x+2,m,rx));
    }

    int get(int l, int r) {
        return get(l,r,0,0,n);
    }

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

    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;

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;
    mnx.init(n,r);mxx.init(n,r);
    mny.init(n,c);mxy.init(n,c);
}

int swap_seats(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
        // cout << sX << " " << eX << " " << sY << " " << eY << endl;
        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);
        // cout << mn << endl;
        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]);
    }
    // cout << endl;

    return cnt+1;
}

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