Submission #1196456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196456		tkm_algorithms	Seats (IOI18_seats)	C++20	31 / 100	3852 ms	40244 KiB

seats

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
using ll = long long;

//bool f(int l, int r) {
	
//}

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int ll

const char nl = '\n';

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

struct segtree {
    int n;
    vector<short int> rmin, rmax, cmin, cmax;

    void init(int size) {
        n = 1;
        while (n < size) n <<= 1;
        rmin.assign(2 * n-1, size);
        rmax.assign(2 * n-1, 0);
        cmin.assign(2 * n-1, size);
        cmax.assign(2 * n-1, 0);
    }

	void build(vector<int> &rr, vector<int> &cc, int x, int lx, int rx) {
		if (rx-lx == 1) {
			if (lx < sz(rr))
				rmin[x] = rmax[x] = rr[lx],
				cmin[x] = cmax[x] = cc[lx];
			return;
		}
		
		int mid = lx+rx>>1;
		build(rr, cc, 2*x+1, lx, mid);
		build(rr, cc, 2*x+2, mid, rx);
		rmin[x] = min(rmin[2*x+1], rmin[2*x+2]);
		cmin[x] = min(cmin[2*x+1], cmin[2*x+2]);
		rmax[x] = max(rmax[2*x+1], rmax[2*x+2]);
		cmax[x] = max(cmax[2*x+1], cmax[2*x+2]);
	}

    void build(vector<int> &rr, vector<int> &cc) {
		build(rr, cc, 0, 0, n);
	}

    void set(int i, int rr, int cc) {
        i = i+n-1;
        rmin[i] = rmax[i] = rr;
        cmin[i] = cmax[i] = cc;
        while (i > 0) {
			i = (i-1)/2;
			rmin[i] = min(rmin[2*i+1], rmin[2*i+2]);
			cmin[i] = min(cmin[2*i+1], cmin[2*i+2]);
			rmax[i] = max(rmax[2*i+1], rmax[2*i+2]);
			cmax[i] = max(cmax[2*i+1], cmax[2*i+2]);
		}
    }
    
	bool lezit(tuple<int, int, int, int> a, tuple<int, int, int, int> b) {
		int x, y, z, q;
		tie(x, y, z, q) = a;
		int m1, m2, m3, m4;
		tie(m1, m2, m3, m4) = b;
		if (m1 >= x && m1 <= y && m2 >= x && m2 <= y)
			if (m3 >= z && m3 <= q && m4 >= z && m4 <= q)return true;
		return false;
	}
    
    tuple<int, int, int, int> get(int l, int rr, int x, int lx, int rx) {
		if (rx <= l || rr <= lx)return {INT_MAX, INT_MIN, INT_MAX, INT_MIN};
		if (lx >= l && rx <= rr)return {rmin[x], rmax[x], cmin[x], cmax[x]};
		int mid = lx+rx>>1;
		int a, b, cc, d;
		tie(a, b, cc, d) = get(l, rr, 2*x+1, lx, mid);
		int xx, y, z, dd;
		tie(xx, y, z, dd) = get(l, rr, 2*x+2, mid, rx);
		return {min(a, xx), max(b, y), min(cc, z), max(d, dd)};
	}
	
	 tuple<int, int, int, int> get(int l, int rr) {
		return get(l, rr, 0, 0, n);
	}
	
	int fnd(int m1, int m2, int m3, int m4, int x, int lx, int rx) {
		if (rx-lx==1) {
			return rx-1;
		}
		
		int mid = (lx + rx >> 1);
		bool ok = true;
		if (!lezit({m1, m2, m3, m4}, {rmin[2*x+1], rmax[2*x+1], cmin[2*x+1], cmax[2*x+1]})) {
			ok = false;
			return fnd(m1, m2, m3, m4, 2*x+1, lx, mid);
		} else {
			if (!lezit({m1, m2, m3, m4}, {rmin[2*x+2], rmax[2*x+2], cmin[2*x+2], cmax[2*x+2]})) {
				ok = false;
				return fnd(m1, m2, m3, m4, 2*x+2, mid, rx);
			}
		}
		
		if (ok) {
			return rx-1;
		}
	}
	
	int fnd(int m1, int m2, int m3, int m4) {
		return fnd(m1, m2, m3, m4, 0, 0, n);
	}
};


segtree st;
//int g[N];

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  r = R, c = C;
  h = H, w = W;

  st.init(h * w);
  st.build(r, c);
}

int swap_seats(int a, int b) {
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	
	st.set(a, r[a], c[a]);
	st.set(b, r[b], c[b]);
	
	int i = 0;
	//int x, y, z, d;
	int m1, m2, m3, m4;
	tie(m1, m2, m3, m4) = {r[0], r[0], c[0], c[0]};
	int g = (m2-m1+1)*(m4-m3+1);
	
	short int ans = 0;
	
	while (i < h*w) {
		if (i+1 == g) {
			ans += 1, i += 1;
		} else
			i = g-1;
		tie(m1, m2, m3, m4) = st.get(0, i+1);
		g = (m2-m1+1)*(m4-m3+1);
	}
	
	return ans;
}


//void solve() {
	//int H, W, Q;
	//cin >> H >> W >> Q;
	
	//vector<int> R, C;
	//R.resize(H*W); C.resize(H*W);
	//for (int i = 0; i < H*W; ++i)cin >> R[i] >> C[i];
	
	//give_initial_chart(H, W, R, C);
	
	//while (Q--) {
		//int a, b; cin >> a >> b;
		//cout << swap_seats(a, b) << nl;
	//}
//}

//int32_t main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //int t = 1;
    //for (int _ = 0; _ < t; ++_) {
        //solve();
    //}
    //return 0;
//}

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