Submission #1196507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196507		tkm_algorithms	Seats (IOI18_seats)	C++17	5 / 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, int x, int lx, int rx) {
		if (rx-lx == 1) {
			tree[x] = {u, u, v, v};
			return;
		}
		
		int mid = lx+rx>>1;
		if (i < mid)set(i, u, v, 2*x+1, lx, mid);
		else set(i, u, v, 2*x+2, mid, rx);
		
		tree[x] = combine(tree[2*x+1], tree[2*x+2]);
	}
	
	void set(int i, int u, int v) {
		set(i, u, v, 0, 0, size);
	}
	
	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);
	}
};

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);
  
  //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;
	tie(x, y, z, d) = {r[0], r[0], c[0], c[0]};
	int g = (x-y+1)*(z-d+1);
	int m1, m2, m3, m4;
	tie(m1, m2, m3, m4) = {r[0], r[0], c[0], c[0]};
	
	int ans = 0;
	
	int cnt = 0;
	
	while (i < h*w) {
		int lx = i+1, rx = h*w;
		while (lx < rx) {
			int mid = lx+rx>>1;
			tie(x, y, z, d) = st.get(0, mid+1);
			if (m1 == x && m2 == y && m3 == z && m4 == d)lx = mid+1;
			else rx = mid;
		}
		int onki = lx-1;
		if (g-onki-1 == 0)ans += 1;
		i = lx;
		
		cnt += 1;
		assert(cnt <= 2*(h+w));
		
		tie(m1, m2, m3, m4) = st.get(0, lx+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: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30