Submission #792804

#	Time	Username	Problem	Language	Result	Execution time	Memory
792804		Sohsoh84	Seats (IOI18_seats)	C++17	31 / 100	4059 ms	102420 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;

int n, m, R[MAXN], C[MAXN], k;
vector<vector<int>> A;
vector<int> sg[MAXN];

inline void update(int t, int ind, int val, int l, int r, int v) {
	if (l == r) sg[t][v] = val;
	else {
		int mid = (l + r) >> 1;
		if (ind <= mid) update(t, ind, val, l, mid, v << 1);
		else update(t, ind, val, mid + 1, r, v << 1 | 1);
		sg[t][v] = max(sg[t][v << 1], sg[t][v << 1 | 1]);
	}
}

inline int query(int t, int ql, int qr, int l, int r, int v) {
	if (ql > r || qr < l) return 0;
	if (ql <= l && qr >= r) return sg[t][v];
	
	int mid = (l + r) >> 1;
	return max(query(t, ql, qr, l, mid, v << 1),
			query(t, ql, qr, mid + 1, r, v << 1 | 1));
		
}

void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_) {
	n = H_, m = W_;
	k = n * m;
	
	for (int i = 0; i < n; i++)
		sg[i].resize(4 * m);

	for (int i = 0; i < m; i++)
		sg[n + i].resize(4 * n);
	
	A.resize(n + 3);
	for (int i = 0; i < n; i++) {
		A[i].resize(m + 3);
	}

	for (int i = 0; i < n * m; i++) {
		R[i] = R_[i];
		C[i] = C_[i];
		A[R[i]][C[i]] = i;

		update(R[i], C[i], i, 0, m - 1, 1);
		update(n + C[i], R[i], i, 0, n - 1, 1);
	}

}

int swap_seats(int a, int b) {	
	swap(A[R[a]][C[a]], A[R[b]][C[b]]);
	swap(R[a], R[b]);
	swap(C[a], C[b]);

	update(R[a], C[a], a, 0, m - 1, 1);
	update(n + C[a], R[a], a, 0, n - 1, 1);	
	update(R[b], C[b], b, 0, m - 1, 1);
	update(n + C[b], R[b], b, 0, n - 1, 1);

	int rl = R[0], rr = R[0], cl = C[0], cr = C[0], mx = 0;
	int ans = 1;

	while (rl > 0 || rr < n - 1 || cl > 0 || cr < m - 1) {
		int best_type = -1, best = numeric_limits<int>::max();
		if (rl > 0) {
			int poss = A[rl - 1][cl];
			if (poss < best) {
				best_type = 0;
				best = poss;
			}
		}

		if (cl > 0) {
			int poss = A[rl][cl - 1];
			if (poss < best) {
				best_type = 1;
				best = poss;
			}
		}

		if (rr < n - 1) {
			int poss = A[rr + 1][cl];
			if (poss < best) {
				best_type = 2;
				best = poss;
			}
		}

		if (cr < m - 1) {
			int poss = A[rl][cr + 1];
			if (poss < best) {
				best_type = 3;
				best = poss;
			}
		}


		if (best_type == 0) {
			rl--;
			mx = max(mx, query(rl, cl, cr, 0, m - 1, 1));
		} else if (best_type == 2) {
			rr++;
			mx = max(mx, query(rr, cl, cr, 0, m - 1, 1));
		} else if (best_type == 1) {
			cl--;
			mx = max(mx, query(n + cl, rl, rr, 0, n - 1, 1));
		} else {
			cr++;
			mx = max(mx, query(n + cr, rl, rr, 0, n - 1, 1));
		}

		if (mx + 1 == (rr - rl + 1) * (cr - cl + 1))
			ans++;
	}

	return ans;
}

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