Submission #1196458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196458		tkm_algorithms	Seats (IOI18_seats)	C++20	25 / 100	4094 ms	56640 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;

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

const char nl = '\n';

const int N = 1e6+10;

vector<int> r, c;
int h, w, p[N];

struct segtree {
	vector<tuple<int, int, int, int>> tree; // rmin, rmax, cmin, cmax.
	int size, hh;
	
	void init(int n) {
		size = 1, hh = n;
		while (size < n)size <<= 1;
		tree.assign(2*size-1, {hh, 0, hh, 0});
	}
	
	tuple<int, int, int, int> combine(tuple<int, int, int, int>a, tuple<int, int, int, int>b) {
		int q, ww, e, rr;
		tie(q, ww, e, rr) = a;
		int q1, w1, e1, r1;
		tie(q1, w1, e1, r1) = b;
		return {min(q, q1), max(ww, w1), min(e, e1), max(rr, r1)};
	}
	
	void build(vector<int> &rr, vector<int> &cc, int x, int lx, int rx) {
		if (rx-lx == 1) {
			if (lx < sz(r))
				tree[x] = {rr[lx], rr[lx], cc[lx], cc[lx]};
			return;
		}
		
		int mid = lx+rx>>1;
		build(rr, cc, 2*x+1, lx, mid);
		build(rr, cc, 2*x+2, mid, rx);
		tree[x] = combine(tree[2*x+1], tree[2*x+2]);
	}
	
	void build(vector<int> &rr, vector<int> &cc) {
		init(sz(rr));
		build(rr, cc, 0, 0, size);
	}
	
	//void set(int i, int u, int v) {
		
	//}
	
	void set(int i, int u, int v) {
		int x = size+i-1;
		tree[x] = {u, u, v, v};
		while (x > 0) {
			x = (x-1)/2;
			tree[x] = combine(tree[2*x+1], tree[2*x+2]);
		}
	}
	
	tuple<int, int, int, int> get(int l, int rr, int x, int lx, int rx) {
		if (rx <= l || rr <= lx)return {hh, 0, hh, 0};
		if (lx >= l && rx <= rr)return tree[x];
		int mid = lx+rx>>1;
		return combine(get(l, rr, 2*x+1, lx, mid), get(l, rr, 2*x+2, mid, rx));
	}
	
	tuple<int, int, int, int> get(int l, int rr) {
		return get(l, rr, 0, 0, size);
	}
	
	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;
	}
	
	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}, tree[2*x+1])) {
			ok = false;
			return fnd(m1, m2, m3, m4, 2*x+1, lx, mid);
		} else {
			if (!lezit({m1, m2, m3, m4}, tree[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, size);
	}
};

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.build(r, c);
  //st.set(1, r[0], c[0]);
  
  
  //for (int i = 0; i < h*w; ++i) {
	//auto yu = st.get(0, i+1);
	//int x, y, z, d;
	//tie(x, y, z, d) = yu;
	//g[i] = (x-y+1)*(z-d+1);
  //}
}

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);
	
	int ans = 0;
	
	while (i < h*w) {
		int lx = st.fnd(m1, m2, m3, m4);
		if (g - (lx-1)-1 == 0)
			ans += 1;
		i = lx;
		tie(m1, m2, m3, m4) = st.get(0, lx+1);
		g = (m2-m1+1)*(m4-m3+1);
	}
	
	return ans+1;
}


//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;
//}

Compilation message (stderr)

seats.cpp: In member function 'int segtree::fnd(int, int, int, int, int, int, int)':
seats.cpp:111:9: warning: control reaches end of non-void function [-Wreturn-type]
  111 |         }
      |         ^

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